home *** CD-ROM | disk | FTP | other *** search
open in:
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: LaTeX Document
(document/latex).
Confidence | Program | Detection | Match Type | Support
|
---|
100%
| dexvert
| LaTeX Document (document/latex)
| magic
| Supported |
100%
| dexvert
| Texinfo Document (document/texInfo)
| magic
| Supported |
1%
| dexvert
| Corel 10 Texture (image/corel10Texture)
| ext
| Unsupported |
1%
| dexvert
| Croteam texture file (image/croteamTextureFile)
| ext
| Unsupported |
1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
100%
| file
| LaTeX document text
| default
| |
99%
| file
| TeX document text
| default
| |
98%
| file
| LaTeX auxiliary file, ASCII text
| default
| |
100%
| TrID
| LaTeX 2e document (with rem)
| default
| |
100%
| checkBytes
| Printable ASCII
| default
| |
100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
100%
| xdgMime
| text/x-matlab
| default (weak)
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 25 20 54 68 69 73 20 69 | 73 20 74 72 65 65 5f 64 |% This i|s tree_d|
|00000010| 6f 63 2e 74 65 78 2c 20 | 74 68 65 20 64 6f 63 75 |oc.tex, |the docu|
|00000020| 6d 65 6e 74 61 74 69 6f | 6e 20 66 6f 72 20 74 68 |mentatio|n for th|
|00000030| 65 20 74 72 65 65 74 65 | 78 20 6d 61 63 72 6f 20 |e treete|x macro |
|00000040| 70 61 63 6b 61 67 65 0a | 25 20 61 73 20 69 74 20 |package.|% as it |
|00000050| 77 69 6c 6c 20 61 70 70 | 65 61 72 20 69 6e 20 74 |will app|ear in t|
|00000060| 68 65 20 63 6f 6e 66 65 | 72 65 6e 63 65 20 70 72 |he confe|rence pr|
|00000070| 6f 63 65 65 64 69 6e 67 | 73 20 6f 66 20 74 68 65 |oceeding|s of the|
|00000080| 20 74 68 69 72 64 20 45 | 75 72 6f 70 65 61 6e 0a | third E|uropean.|
|00000090| 25 20 54 65 58 20 6d 65 | 65 74 69 6e 67 20 69 6e |% TeX me|eting in|
|000000a0| 20 45 78 65 74 65 72 2c | 20 45 6e 67 6c 61 6e 64 | Exeter,| England|
|000000b0| 2c 20 31 39 38 38 2e 0a | 0a 5c 64 6f 63 75 6d 65 |, 1988..|.\docume|
|000000c0| 6e 74 73 74 79 6c 65 5b | 31 32 70 74 2c 44 49 4e |ntstyle[|12pt,DIN|
|000000d0| 2d 41 34 5d 7b 61 72 74 | 69 63 6c 65 7d 20 0a 0a |-A4]{art|icle} ..|
|000000e0| 5c 61 64 76 61 6e 63 65 | 5c 76 6f 66 66 73 65 74 |\advance|\voffset|
|000000f0| 20 62 79 20 2d 32 63 6d | 20 20 20 20 20 20 20 20 | by -2cm| |
|00000100| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000110| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000120| 20 20 20 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00000130| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000140| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000160| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000170| 20 20 20 20 0a 5c 63 6c | 75 62 70 65 6e 61 6c 74 | .\cl|ubpenalt|
|00000180| 79 3d 31 30 30 30 30 20 | 20 20 20 20 20 20 20 20 |y=10000 | |
|00000190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000001a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000001b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000001c0| 20 20 20 20 20 0a 5c 77 | 69 64 6f 77 70 65 6e 61 | .\w|idowpena|
|000001d0| 6c 74 79 3d 31 30 30 30 | 30 20 20 20 20 20 20 20 |lty=1000|0 |
|000001e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000001f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000200| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000210| 20 20 20 20 20 20 0a 5c | 64 65 66 5c 61 64 64 63 | .\|def\addc|
|00000220| 6f 6e 74 65 6e 74 73 6c | 69 6e 65 23 31 23 32 23 |ontentsl|ine#1#2#|
|00000230| 33 7b 5c 72 65 6c 61 78 | 7d 25 20 53 6f 6d 65 20 |3{\relax|}% Some |
|00000240| 63 61 70 74 69 6f 6e 73 | 20 61 72 65 20 74 6f 6f |captions| are too|
|00000250| 20 6c 6f 6e 67 20 66 6f | 72 20 73 6f 6d 65 0a 20 | long fo|r some. |
|00000260| 20 20 20 20 25 20 54 65 | 58 20 69 6e 73 74 61 6c | % Te|X instal|
|00000270| 6c 61 74 69 6f 6e 73 20 | 28 62 75 66 66 65 72 20 |lations |(buffer |
|00000280| 73 69 7a 65 20 74 6f 6f | 20 73 6d 61 6c 6c 29 0a |size too| small).|
|00000290| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|000002a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000002b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000002c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000002d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000002e0| 20 0a 5c 6e 65 77 65 6e | 76 69 72 6f 6e 6d 65 6e | .\newen|vironmen|
|000002f0| 74 7b 6c 65 6d 6d 61 7d | 7b 5c 62 65 67 69 6e 67 |t{lemma}|{\beging|
|00000300| 72 6f 75 70 5c 73 61 6d | 65 70 61 67 65 5c 62 65 |roup\sam|epage\be|
|00000310| 67 69 6e 7b 6c 65 6d 6d | 6d 61 7d 5c 20 7d 7b 5c |gin{lemm|ma}\ }{\|
|00000320| 65 6e 64 7b 6c 65 6d 6d | 6d 61 7d 25 20 20 20 20 |end{lemm|ma}% |
|00000330| 20 20 0a 20 20 20 20 20 | 5c 65 6e 64 67 72 6f 75 | . |\endgrou|
|00000340| 70 7d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |p} | |
|00000350| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000360| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000370| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000380| 20 20 20 0a 5c 6e 65 77 | 74 68 65 6f 72 65 6d 7b | .\new|theorem{|
|00000390| 6c 65 6d 6d 6d 61 7d 7b | 4c 65 6d 6d 61 7d 5b 73 |lemmma}{|Lemma}[s|
|000003a0| 65 63 74 69 6f 6e 5d 20 | 20 20 20 20 20 20 20 20 |ection] | |
|000003b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000003c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000003d0| 20 20 20 20 0a 5c 6e 65 | 77 65 6e 76 69 72 6f 6e | .\ne|wenviron|
|000003e0| 6d 65 6e 74 7b 70 72 6f | 6f 66 7d 7b 5c 62 65 67 |ment{pro|of}{\beg|
|000003f0| 69 6e 7b 70 72 6f 6f 6f | 66 7d 5c 72 6d 5c 20 5c |in{prooo|f}\rm\ \|
|00000400| 6e 6f 70 61 67 65 62 72 | 65 61 6b 7d 7b 5c 65 6e |nopagebr|eak}{\en|
|00000410| 64 7b 70 72 6f 6f 6f 66 | 7d 7d 20 20 20 20 20 20 |d{prooof|}} |
|00000420| 20 20 20 20 20 0a 5c 6e | 65 77 63 6f 6d 6d 61 6e | .\n|ewcomman|
|00000430| 64 7b 5c 70 72 6f 6f 66 | 65 6e 64 7d 7b 5c 71 71 |d{\proof|end}{\qq|
|00000440| 75 61 64 5c 69 66 6d 6d | 6f 64 65 5c 42 6f 78 5c |uad\ifmm|ode\Box\|
|00000450| 65 6c 73 65 24 5c 42 6f | 78 24 5c 66 69 7d 20 20 |else$\Bo|x$\fi} |
|00000460| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000470| 20 20 20 20 20 20 0a 5c | 6e 65 77 74 68 65 6f 72 | .\|newtheor|
|00000480| 65 6d 7b 70 72 6f 6f 6f | 66 7d 7b 50 72 6f 6f 66 |em{prooo|f}{Proof|
|00000490| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|000004a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000004b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000004c0| 20 20 20 20 20 20 20 0a | 5c 72 65 6e 65 77 63 6f | .|\renewco|
|000004d0| 6d 6d 61 6e 64 7b 5c 74 | 68 65 70 72 6f 6f 6f 66 |mmand{\t|heprooof|
|000004e0| 7d 7b 7d 20 20 20 25 20 | 6d 61 6b 65 73 20 73 68 |}{} % |makes sh|
|000004f0| 75 72 65 20 74 68 61 74 | 20 70 72 6f 6f 6f 66 20 |ure that| prooof |
|00000500| 64 6f 65 73 6e 27 74 20 | 67 65 74 20 6e 75 6d 62 |doesn't |get numb|
|00000510| 65 72 73 20 20 20 20 20 | 20 20 0a 5c 6e 65 77 65 |ers | .\newe|
|00000520| 6e 76 69 72 6f 6e 6d 65 | 6e 74 7b 46 69 67 75 72 |nvironme|nt{Figur|
|00000530| 65 7d 7b 5c 62 65 67 69 | 6e 7b 66 69 67 75 72 65 |e}{\begi|n{figure|
|00000540| 7d 5c 76 73 70 61 63 65 | 7b 31 5c 62 61 73 65 6c |}\vspace|{1\basel|
|00000550| 69 6e 65 73 6b 69 70 7d | 7d 25 20 20 20 20 20 20 |ineskip}|}% |
|00000560| 20 20 20 20 20 20 20 20 | 20 20 20 0a 20 20 20 20 | | . |
|00000570| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000580| 20 20 20 7b 5c 76 73 70 | 61 63 65 7b 31 5c 62 61 | {\vsp|ace{1\ba|
|00000590| 73 65 6c 69 6e 65 73 6b | 69 70 7d 5c 65 6e 64 7b |selinesk|ip}\end{|
|000005a0| 66 69 67 75 72 65 7d 7d | 20 20 20 20 20 20 20 20 |figure}}| |
|000005b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 6e 65 | | .\ne|
|000005c0| 77 6c 65 6e 67 74 68 7b | 5c 66 69 67 73 70 61 63 |wlength{|\figspac|
|000005d0| 65 7d 20 20 20 20 20 20 | 20 20 20 25 20 73 70 61 |e} | % spa|
|000005e0| 63 65 20 62 65 74 77 65 | 65 6e 20 66 69 67 75 72 |ce betwe|en figur|
|000005f0| 65 73 20 69 6e 20 61 20 | 73 69 6e 67 6c 65 20 20 |es in a |single |
|00000600| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 5c 73 | | .\s|
|00000610| 65 74 6c 65 6e 67 74 68 | 7b 5c 66 69 67 73 70 61 |etlength|{\figspa|
|00000620| 63 65 7d 7b 33 30 70 74 | 7d 20 20 20 25 20 46 69 |ce}{30pt|} % Fi|
|00000630| 67 75 72 65 20 65 6e 76 | 69 72 6f 6e 6d 65 6e 74 |gure env|ironment|
|00000640| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000650| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 20 | | . |
|00000660| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000670| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000680| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000690| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000006a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|000006b0| 5c 6e 65 77 63 6f 6d 6d | 61 6e 64 7b 5c 76 61 72 |\newcomm|and{\var|
|000006c0| 7d 5b 31 5d 7b 7b 5c 69 | 74 20 23 31 5c 2f 7d 7d |}[1]{{\i|t #1\/}}|
|000006d0| 20 20 20 20 20 25 20 75 | 73 65 20 69 74 20 66 6f | % u|se it fo|
|000006e0| 72 20 6e 61 6d 65 73 20 | 6f 66 20 76 61 72 69 61 |r names |of varia|
|000006f0| 62 6c 65 73 20 20 20 20 | 20 20 20 20 20 20 20 20 |bles | |
|00000700| 0a 5c 6e 65 77 63 6f 6d | 6d 61 6e 64 7b 5c 65 6d |.\newcom|mand{\em|
|00000710| 70 68 7d 5b 31 5d 7b 7b | 5c 65 6d 20 23 31 5c 2f |ph}[1]{{|\em #1\/|
|00000720| 7d 7d 20 20 20 20 25 20 | 75 73 65 20 69 74 20 66 |}} % |use it f|
|00000730| 6f 72 20 65 6d 70 68 61 | 7a 69 64 65 64 20 74 65 |or empha|zided te|
|00000740| 78 74 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |xt | |
|00000750| 20 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00000760| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000770| 20 20 20 20 20 20 20 25 | 20 28 54 68 69 73 20 6e | %| (This n|
|00000780| 6f 74 69 6f 6e 20 73 74 | 69 63 6b 73 20 74 6f 20 |otion st|icks to |
|00000790| 74 68 65 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |the | |
|000007a0| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|000007b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000007c0| 20 20 20 20 20 20 20 20 | 25 20 61 70 70 6c 69 63 | |% applic|
|000007d0| 61 74 69 76 65 20 73 74 | 79 6c 65 20 6f 66 20 6d |ative st|yle of m|
|000007e0| 61 72 6b 75 70 2e 29 20 | 20 20 20 20 20 20 20 20 |arkup.) | |
|000007f0| 20 20 20 0a 5c 72 65 6e | 65 77 63 6f 6d 6d 61 6e | .\ren|ewcomman|
|00000800| 64 7b 5c 4f 7d 7b 7b 5c | 72 6d 20 4f 7d 7d 20 20 |d{\O}{{\|rm O}} |
|00000810| 20 20 20 20 20 20 20 20 | 20 25 20 4f 2d 6e 6f 74 | | % O-not|
|00000820| 61 74 69 6f 6e 2c 20 61 | 6c 73 6f 20 66 6f 72 20 |ation, a|lso for |
|00000830| 6d 61 74 68 20 6d 6f 64 | 65 20 20 20 20 20 20 20 |math mod|e |
|00000840| 20 20 20 20 0a 5c 6e 65 | 77 63 6f 6d 6d 61 6e 64 | .\ne|wcommand|
|00000850| 7b 5c 54 7d 7b 7b 5c 63 | 61 6c 20 54 7d 7d 20 20 |{\T}{{\c|al T}} |
|00000860| 20 20 20 20 20 20 20 20 | 20 20 25 20 74 68 65 20 | | % the |
|00000870| 73 65 74 20 54 20 69 6e | 20 6d 61 74 68 20 6d 6f |set T in| math mo|
|00000880| 64 65 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |de | |
|00000890| 20 20 20 20 20 0a 5c 6e | 65 77 63 6f 6d 6d 61 6e | .\n|ewcomman|
|000008a0| 64 7b 5c 54 72 65 65 54 | 65 58 7d 7b 54 72 65 65 |d{\TreeT|eX}{Tree|
|000008b0| 5c 54 65 58 7d 20 20 20 | 20 20 20 20 20 20 20 20 |\TeX} | |
|000008c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000008d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000008e0| 20 20 20 20 20 20 0a 5c | 6e 65 77 63 6f 6d 6d 61 | .\|newcomma|
|000008f0| 6e 64 7b 5c 66 69 67 7d | 5b 31 5d 7b 46 69 67 75 |nd{\fig}|[1]{Figu|
|00000900| 72 65 7e 5c 72 65 66 7b | 23 31 7d 7d 20 20 20 20 |re~\ref{|#1}} |
|00000910| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000920| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000930| 20 20 20 20 20 20 20 0a | 5c 6c 65 74 5c 70 5c 70 | .|\let\p\p|
|00000940| 61 72 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ar | |
|00000950| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000960| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000970| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000980| 20 20 20 20 20 20 20 20 | 0a 20 20 20 20 20 20 20 | |. |
|00000990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000009a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000009b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000009c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000009d0| 20 20 20 20 20 20 20 20 | 20 0a 5c 69 6e 70 75 74 | | .\input|
|000009e0| 20 54 72 65 65 54 65 58 | 20 20 20 20 20 20 20 20 | TreeTeX| |
|000009f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 54 72 | | .\Tr|
|00000a10| 65 65 73 74 79 6c 65 7b | 5c 76 64 69 73 74 7b 32 |eestyle{|\vdist{2|
|00000a20| 30 70 74 7d 5c 6d 69 6e | 73 65 70 7b 31 36 70 74 |0pt}\min|sep{16pt|
|00000a30| 7d 7d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |}} | |
|00000a40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000a50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000a60| 20 20 20 20 20 20 20 20 | 20 20 0a 5c 64 75 6d 6d | | .\dumm|
|00000a70| 79 68 61 6c 66 63 65 6e | 74 65 72 64 69 6d 40 6e |yhalfcen|terdim@n|
|00000a80| 3d 32 70 74 20 20 20 20 | 20 20 20 20 20 20 20 20 |=2pt | |
|00000a90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000aa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ab0| 20 20 20 20 20 20 20 20 | 20 20 20 0a 20 20 20 20 | | . |
|00000ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ad0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ae0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000af0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 64 65 | | .\de|
|00000b10| 66 5c 4e 6f 64 65 28 23 | 31 2c 23 32 29 7b 5c 70 |f\Node(#|1,#2){\p|
|00000b20| 75 74 28 23 31 2c 23 32 | 29 7b 5c 63 69 72 63 6c |ut(#1,#2|){\circl|
|00000b30| 65 2a 7b 34 7d 7d 7d 20 | 20 20 20 20 20 20 20 20 |e*{4}}} | |
|00000b40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000b50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 5c 64 | | .\d|
|00000b60| 65 66 5c 45 64 67 65 28 | 23 31 2c 23 32 2c 23 33 |ef\Edge(|#1,#2,#3|
|00000b70| 2c 23 34 2c 23 35 29 7b | 5c 70 75 74 28 23 31 2c |,#4,#5){|\put(#1,|
|00000b80| 23 32 29 7b 5c 6c 69 6e | 65 28 23 33 2c 23 34 29 |#2){\lin|e(#3,#4)|
|00000b90| 7b 23 35 7d 7d 7d 20 20 | 20 20 20 20 20 20 20 20 |{#5}}} | |
|00000ba0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 20 | | . |
|00000bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000bc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000bd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000be0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000bf0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00000c00| 5c 64 65 66 5c 65 6e 6f | 64 65 7b 5c 6e 6f 64 65 |\def\eno|de{\node|
|00000c10| 7b 5c 65 78 74 65 72 6e | 61 6c 5c 74 79 70 65 7b |{\extern|al\type{|
|00000c20| 64 6f 74 7d 7d 7d 20 20 | 20 20 20 20 20 20 20 20 |dot}}} | |
|00000c30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000c40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000c50| 0a 5c 64 65 66 5c 69 6e | 6f 64 65 7b 5c 6e 6f 64 |.\def\in|ode{\nod|
|00000c60| 65 7b 5c 74 79 70 65 7b | 64 6f 74 7d 7d 7d 20 20 |e{\type{|dot}}} |
|00000c70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000c80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000c90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ca0| 20 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00000cb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000cd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ce0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000cf0| 20 20 0a 5c 64 65 66 5c | 65 7b 5c 6e 6f 64 65 7b | .\def\|e{\node{|
|00000d00| 5c 65 78 74 65 72 6e 61 | 6c 5c 74 79 70 65 7b 64 |\externa|l\type{d|
|00000d10| 6f 74 7d 7d 7d 20 20 20 | 20 20 20 20 20 20 20 20 |ot}}} | |
|00000d20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000d30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000d40| 20 20 20 0a 5c 64 65 66 | 5c 69 7b 5c 6e 6f 64 65 | .\def|\i{\node|
|00000d50| 7b 5c 74 79 70 65 7b 64 | 6f 74 7d 7d 7d 20 20 20 |{\type{d|ot}}} |
|00000d60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000d70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000d80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000d90| 20 20 20 20 0a 5c 64 65 | 66 5c 69 6c 7b 5c 6e 6f | .\de|f\il{\no|
|00000da0| 64 65 7b 5c 74 79 70 65 | 7b 64 6f 74 7d 5c 6c 65 |de{\type|{dot}\le|
|00000db0| 66 74 6f 6e 6c 79 7d 7d | 20 20 20 20 20 20 20 20 |ftonly}}| |
|00000dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000de0| 20 20 20 20 20 0a 5c 64 | 65 66 5c 69 72 7b 5c 6e | .\d|ef\ir{\n|
|00000df0| 6f 64 65 7b 5c 74 79 70 | 65 7b 64 6f 74 7d 5c 72 |ode{\typ|e{dot}\r|
|00000e00| 69 67 68 74 6f 6e 6c 79 | 7d 7d 20 20 20 20 20 20 |ightonly|}} |
|00000e10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e30| 20 20 20 20 20 20 0a 20 | 20 20 20 20 20 20 20 20 | . | |
|00000e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000e80| 20 20 20 20 20 20 20 0a | 5c 6e 65 77 63 6f 6d 6d | .|\newcomm|
|00000e90| 61 6e 64 7b 5c 73 74 61 | 63 6b 7d 5b 33 5d 7b 25 |and{\sta|ck}[3]{%|
|00000ea0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000eb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ec0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ed0| 20 20 20 20 20 20 20 20 | 0a 20 20 20 20 20 5c 76 | |. \v|
|00000ee0| 74 6f 70 7b 5c 73 65 74 | 74 6f 77 69 64 74 68 7b |top{\set|towidth{|
|00000ef0| 5c 68 73 69 7a 65 7d 7b | 23 31 7d 25 20 20 20 20 |\hsize}{|#1}% |
|00000f00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f20| 20 20 20 20 20 20 20 20 | 20 0a 20 20 20 20 20 5c | | . \|
|00000f30| 73 65 74 6c 65 6e 67 74 | 68 7b 5c 6c 65 66 74 73 |setlengt|h{\lefts|
|00000f40| 6b 69 70 7d 7b 30 70 74 | 20 70 6c 75 73 20 31 66 |kip}{0pt| plus 1f|
|00000f50| 69 6c 6c 7d 25 20 20 20 | 20 20 20 20 20 20 20 20 |ill}% | |
|00000f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f70| 20 20 20 20 20 20 20 20 | 20 20 0a 20 20 20 20 20 | | . |
|00000f80| 5c 73 65 74 6c 65 6e 67 | 74 68 7b 5c 62 61 73 65 |\setleng|th{\base|
|00000f90| 6c 69 6e 65 73 6b 69 70 | 7d 7b 23 32 7d 23 33 7d |lineskip|}{#2}#3}|
|00000fa0| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|00000fb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000fc0| 20 20 20 20 20 20 20 20 | 20 20 20 0a 20 20 20 20 | | . |
|00000fd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000fe0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000ff0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001010| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 6c 65 | | .\le|
|00001020| 74 5c 6d 75 6c 74 69 63 | 5c 6d 75 6c 74 69 63 6f |t\multic|\multico|
|00001030| 6c 75 6d 6e 20 20 20 20 | 20 20 20 20 20 20 20 20 |lumn | |
|00001040| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001050| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 | | . |
|00001070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001080| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001090| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000010a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000010b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 5c | | .\|
|000010c0| 6e 65 77 6c 65 6e 67 74 | 68 7b 5c 68 64 7d 20 25 |newlengt|h{\hd} %|
|000010d0| 20 68 69 64 64 65 6e 20 | 64 69 67 69 74 20 20 20 | hidden |digit |
|000010e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000010f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001100| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00001110| 5c 73 65 74 62 6f 78 30 | 5c 68 62 6f 78 7b 31 7d |\setbox0|\hbox{1}|
|00001120| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001130| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001140| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001160| 0a 5c 73 65 74 74 6f 77 | 69 64 74 68 7b 5c 68 64 |.\settow|idth{\hd|
|00001170| 7d 7b 5c 75 73 65 62 6f | 78 7b 30 7d 7d 20 20 20 |}{\usebo|x{0}} |
|00001180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000011a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000011b0| 20 0a 5c 6e 65 77 63 6f | 6d 6d 61 6e 64 7b 5c 64 | .\newco|mmand{\d|
|000011c0| 73 7d 7b 5c 68 73 70 61 | 63 65 7b 5c 68 64 7d 7d |s}{\hspa|ce{\hd}}|
|000011d0| 20 25 20 64 69 67 69 74 | 20 73 70 61 63 65 20 20 | % digit| space |
|000011e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000011f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001200| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00001210| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001220| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001230| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001240| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001250| 20 20 20 0a 5c 6e 65 77 | 63 6f 6d 6d 61 6e 64 7b | .\new|command{|
|00001260| 5c 63 63 6f 6c 7d 5b 31 | 5d 7b 5c 6d 75 6c 74 69 |\ccol}[1|]{\multi|
|00001270| 63 6f 6c 75 6d 6e 7b 31 | 7d 7b 63 7d 7b 23 31 7d |column{1|}{c}{#1}|
|00001280| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|00001290| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000012a0| 20 20 20 20 0a 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|000012b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000012c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000012d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000012e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000012f0| 20 20 20 20 20 0a 5c 68 | 79 70 68 65 6e 61 74 69 | .\h|yphenati|
|00001300| 6f 6e 7b 70 6f 73 74 2d | 6f 72 2d 64 65 72 20 73 |on{post-|or-der s|
|00001310| 79 6d 2d 62 6f 6c 20 4b | 61 72 6c 73 2d 72 75 68 |ym-bol K|arls-ruh|
|00001320| 65 20 62 6f 6f 6c 2d 65 | 61 6e 7d 20 20 20 20 20 |e bool-e|an} |
|00001330| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001340| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00001350| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001360| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001370| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001380| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001390| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000013a0| 0a 5c 62 65 67 69 6e 7b | 64 6f 63 75 6d 65 6e 74 |.\begin{|document|
|000013b0| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|000013c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000013d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000013e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000013f0| 20 0a 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00001400| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001410| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001420| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001430| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001440| 20 20 0a 5c 62 69 62 6c | 69 6f 67 72 61 70 68 79 | .\bibl|iography|
|00001450| 73 74 79 6c 65 7b 70 6c | 61 69 6e 7d 20 20 20 20 |style{pl|ain} |
|00001460| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001470| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001480| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001490| 20 20 20 0a 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|000014a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000014e0| 20 20 20 20 0a 5c 74 69 | 74 6c 65 7b 44 72 61 77 | .\ti|tle{Draw|
|000014f0| 69 6e 67 20 54 72 65 65 | 73 20 4e 69 63 65 6c 79 |ing Tree|s Nicely|
|00001500| 20 77 69 74 68 20 5c 54 | 65 58 5c 74 68 61 6e 6b | with \T|eX\thank|
|00001510| 73 7b 54 68 69 73 20 77 | 6f 72 6b 20 77 61 73 20 |s{This w|ork was |
|00001520| 73 75 70 70 6f 72 74 65 | 64 20 62 79 20 20 20 20 |supporte|d by |
|00001530| 20 20 20 20 20 0a 20 20 | 20 20 20 61 20 4e 61 74 | . | a Nat|
|00001540| 75 72 61 6c 20 53 63 69 | 65 6e 63 65 73 20 61 6e |ural Sci|ences an|
|00001550| 64 20 45 6e 67 69 6e 65 | 65 72 69 6e 67 20 52 65 |d Engine|ering Re|
|00001560| 73 65 61 72 63 68 20 43 | 6f 75 6e 63 69 6c 20 6f |search C|ouncil o|
|00001570| 66 20 43 61 6e 61 64 61 | 20 20 20 20 20 20 20 20 |f Canada| |
|00001580| 20 20 20 20 20 20 0a 20 | 20 20 20 20 47 72 61 6e | . | Gran|
|00001590| 74 7e 41 2d 35 36 39 32 | 20 61 6e 64 20 61 20 44 |t~A-5692| and a D|
|000015a0| 65 75 74 73 63 68 65 20 | 46 6f 72 73 63 68 75 6e |eutsche |Forschun|
|000015b0| 67 73 67 65 6d 65 69 6e | 73 63 68 61 66 74 20 47 |gsgemein|schaft G|
|000015c0| 72 61 6e 74 7e 53 74 6f | 31 36 37 2f 31 2d 31 2e |rant~Sto|167/1-1.|
|000015d0| 0a 20 20 20 20 20 49 74 | 20 77 61 73 20 73 74 61 |. It| was sta|
|000015e0| 72 74 65 64 20 64 75 72 | 69 6e 67 20 74 68 65 20 |rted dur|ing the |
|000015f0| 66 69 72 73 74 20 61 75 | 74 68 6f 72 27 73 20 73 |first au|thor's s|
|00001600| 74 61 79 20 77 69 74 68 | 20 20 20 20 20 20 20 20 |tay with| |
|00001610| 20 20 20 20 20 20 0a 20 | 20 20 20 20 74 68 65 20 | . | the |
|00001620| 44 61 74 61 20 53 74 72 | 75 63 74 75 72 69 6e 67 |Data Str|ucturing|
|00001630| 20 47 72 6f 75 70 20 69 | 6e 20 57 61 74 65 72 6c | Group i|n Waterl|
|00001640| 6f 6f 2e 7d 7d 20 20 20 | 20 20 20 20 20 20 20 20 |oo.}} | |
|00001650| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 5c 61 | | .\a|
|00001660| 75 74 68 6f 72 7b 41 6e | 6e 65 20 42 72 5c 22 75 |uthor{An|ne Br\"u|
|00001670| 67 67 65 6d 61 6e 6e 2d | 4b 6c 65 69 6e 5c 74 68 |ggemann-|Klein\th|
|00001680| 61 6e 6b 73 7b 49 6e 73 | 74 69 74 75 74 20 66 5c |anks{Ins|titut f\|
|00001690| 22 75 72 20 49 6e 66 6f | 72 6d 61 74 69 6b 2c 20 |"ur Info|rmatik, |
|000016a0| 20 20 20 20 0a 20 20 20 | 20 20 55 6e 69 76 65 72 | . | Univer|
|000016b0| 73 69 74 5c 22 61 74 20 | 46 72 65 69 62 75 72 67 |sit\"at |Freiburg|
|000016c0| 2c 20 52 68 65 69 6e 73 | 74 72 2e 7e 31 30 2d 2d |, Rheins|tr.~10--|
|000016d0| 31 32 2c 20 37 38 30 30 | 7e 46 72 65 69 62 75 72 |12, 7800|~Freibur|
|000016e0| 67 2c 0a 20 20 20 20 20 | 57 65 73 74 7e 47 65 72 |g,. |West~Ger|
|000016f0| 6d 61 6e 79 7d 5c 20 5c | 61 6e 64 20 44 65 72 69 |many}\ \|and Deri|
|00001700| 63 6b 20 57 6f 6f 64 5c | 74 68 61 6e 6b 73 7b 44 |ck Wood\|thanks{D|
|00001710| 61 74 61 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 |ata | . |
|00001720| 20 20 20 53 74 72 75 63 | 74 75 72 69 6e 67 20 47 | Struc|turing G|
|00001730| 72 6f 75 70 2c 20 44 65 | 70 61 72 74 6d 65 6e 74 |roup, De|partment|
|00001740| 20 6f 66 20 43 6f 6d 70 | 75 74 65 72 20 53 63 69 | of Comp|uter Sci|
|00001750| 65 6e 63 65 2c 20 55 6e | 69 76 65 72 73 69 74 79 |ence, Un|iversity|
|00001760| 20 6f 66 20 20 20 20 20 | 20 20 20 20 20 20 0a 20 | of | . |
|00001770| 20 20 20 20 57 61 74 65 | 72 6c 6f 6f 2c 20 57 61 | Wate|rloo, Wa|
|00001780| 74 65 72 6c 6f 6f 2c 20 | 4f 6e 74 61 72 69 6f 2c |terloo, |Ontario,|
|00001790| 20 4e 32 4c 7e 33 47 31 | 2c 20 43 61 6e 61 64 61 | N2L~3G1|, Canada|
|000017a0| 7d 7d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |}} | |
|000017b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|000017c0| 5c 6d 61 6b 65 74 69 74 | 6c 65 20 20 20 20 20 20 |\maketit|le |
|000017d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000017e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000017f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001800| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001810| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00001820| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001830| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001840| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001850| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001860| 20 0a 5c 62 65 67 69 6e | 7b 61 62 73 74 72 61 63 | .\begin|{abstrac|
|00001870| 74 7d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |t} | |
|00001880| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001890| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018b0| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|000018c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000018f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001900| 20 20 20 0a 56 61 72 69 | 6f 75 73 20 61 6c 67 6f | .Vari|ous algo|
|00001910| 72 69 74 68 6d 73 20 68 | 61 76 65 20 62 65 65 6e |rithms h|ave been|
|00001920| 20 70 72 6f 70 6f 73 65 | 64 20 66 6f 72 20 74 68 | propose|d for th|
|00001930| 65 20 64 69 66 66 69 63 | 75 6c 74 20 70 72 6f 62 |e diffic|ult prob|
|00001940| 6c 65 6d 20 6f 66 20 20 | 20 20 20 20 20 20 20 20 |lem of | |
|00001950| 20 20 20 20 0a 70 72 6f | 64 75 63 69 6e 67 20 61 | .pro|ducing a|
|00001960| 65 73 74 68 65 74 69 63 | 61 6c 6c 79 20 70 6c 65 |esthetic|ally ple|
|00001970| 61 73 69 6e 67 20 64 72 | 61 77 69 6e 67 73 20 6f |asing dr|awings o|
|00001980| 66 20 74 72 65 65 73 2c | 20 73 65 65 7e 25 20 20 |f trees,| see~% |
|00001990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000019a0| 20 20 20 20 20 0a 5c 63 | 69 74 65 7b 54 69 64 69 | .\c|ite{Tidi|
|000019b0| 65 72 54 72 65 65 73 2c | 54 69 64 79 54 72 65 65 |erTrees,|TidyTree|
|000019c0| 73 7d 20 62 75 74 20 20 | 20 20 20 20 20 20 20 20 |s} but | |
|000019d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000019e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000019f0| 20 20 20 20 20 20 0a 69 | 6d 70 6c 65 6d 65 6e 74 | .i|mplement|
|00001a00| 61 74 69 6f 6e 73 20 6f | 6e 6c 79 20 65 78 69 73 |ations o|nly exis|
|00001a10| 74 20 61 73 20 60 60 73 | 70 65 63 69 61 6c 20 70 |t as ``s|pecial p|
|00001a20| 75 72 70 6f 73 65 20 73 | 6f 66 74 77 61 72 65 27 |urpose s|oftware'|
|00001a30| 27 2c 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |', | |
|00001a40| 20 20 20 20 20 20 20 0a | 64 65 73 69 67 6e 65 64 | .|designed|
|00001a50| 20 66 6f 72 20 73 70 65 | 63 69 61 6c 20 65 6e 76 | for spe|cial env|
|00001a60| 69 72 6f 6e 6d 65 6e 74 | 73 2e 20 54 68 65 72 65 |ironment|s. There|
|00001a70| 66 6f 72 65 2c 20 20 20 | 20 20 20 20 20 20 20 20 |fore, | |
|00001a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001a90| 20 20 20 20 20 20 20 20 | 0a 6d 61 6e 79 20 75 73 | |.many us|
|00001aa0| 65 72 73 20 72 65 73 6f | 72 74 20 74 6f 20 74 68 |ers reso|rt to th|
|00001ab0| 65 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e | |
|00001ac0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001ad0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001ae0| 20 20 20 20 20 20 20 20 | 20 0a 64 72 61 77 69 6e | | .drawin|
|00001af0| 67 20 66 61 63 69 6c 69 | 74 69 65 73 20 61 76 61 |g facili|ties ava|
|00001b00| 69 6c 61 62 6c 65 20 6f | 6e 20 6d 6f 73 74 20 70 |ilable o|n most p|
|00001b10| 65 72 73 6f 6e 61 6c 20 | 63 6f 6d 70 75 74 65 72 |ersonal |computer|
|00001b20| 73 2c 20 62 75 74 20 74 | 68 65 20 20 20 20 20 20 |s, but t|he |
|00001b30| 20 20 20 20 20 20 20 20 | 20 20 0a 66 69 67 75 72 | | .figur|
|00001b40| 65 73 20 6f 62 74 61 69 | 6e 65 64 20 69 6e 20 74 |es obtai|ned in t|
|00001b50| 68 69 73 20 77 61 79 20 | 73 74 69 6c 6c 20 6c 6f |his way |still lo|
|00001b60| 6f 6b 20 60 60 68 61 6e | 64 2d 64 72 61 77 6e 27 |ok ``han|d-drawn'|
|00001b70| 27 3b 20 74 68 65 69 72 | 20 71 75 61 6c 69 74 79 |'; their| quality|
|00001b80| 20 69 73 20 20 20 20 20 | 20 20 20 0a 69 6e 66 65 | is | .infe|
|00001b90| 72 69 6f 72 20 74 6f 20 | 74 68 65 20 71 75 61 6c |rior to |the qual|
|00001ba0| 69 74 79 20 6f 66 20 74 | 68 65 20 73 75 72 72 6f |ity of t|he surro|
|00001bb0| 75 6e 64 69 6e 67 20 74 | 65 78 74 20 74 68 61 74 |unding t|ext that|
|00001bc0| 20 63 61 6e 20 62 65 20 | 72 65 61 6c 69 7a 65 64 | can be |realized|
|00001bd0| 20 62 79 20 20 20 20 20 | 20 20 20 20 0a 74 6f 64 | by | .tod|
|00001be0| 61 79 27 73 20 68 69 67 | 68 20 71 75 61 6c 69 74 |ay's hig|h qualit|
|00001bf0| 79 20 74 65 78 74 20 70 | 72 6f 63 65 73 73 69 6e |y text p|rocessin|
|00001c00| 67 20 73 79 73 74 65 6d | 73 2e 20 20 20 20 20 20 |g system|s. |
|00001c10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 | | . |
|00001c30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001c70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 49 | | .I|
|00001c80| 6e 20 74 68 69 73 20 70 | 61 70 65 72 20 77 65 20 |n this p|aper we |
|00001c90| 70 72 65 73 65 6e 74 20 | 61 6e 20 65 6e 74 69 72 |present |an entir|
|00001ca0| 65 6c 79 20 6e 65 77 20 | 73 6f 6c 75 74 69 6f 6e |ely new |solution|
|00001cb0| 20 74 68 61 74 20 20 20 | 20 20 20 20 20 20 20 20 | that | |
|00001cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00001cd0| 69 6e 74 65 67 72 61 74 | 65 73 20 61 20 74 72 65 |integrat|es a tre|
|00001ce0| 65 20 64 72 61 77 69 6e | 67 20 61 6c 67 6f 72 69 |e drawin|g algori|
|00001cf0| 74 68 6d 20 69 6e 74 6f | 20 6f 6e 65 20 6f 66 20 |thm into| one of |
|00001d00| 74 68 65 20 62 65 73 74 | 20 74 65 78 74 20 20 20 |the best| text |
|00001d10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00001d20| 0a 70 72 6f 63 65 73 73 | 69 6e 67 20 73 79 73 74 |.process|ing syst|
|00001d30| 65 6d 73 20 61 76 61 69 | 6c 61 62 6c 65 2e 20 4d |ems avai|lable. M|
|00001d40| 6f 72 65 20 70 72 65 63 | 69 73 65 6c 79 2c 20 77 |ore prec|isely, w|
|00001d50| 65 20 70 72 65 73 65 6e | 74 20 61 20 5c 54 65 58 |e presen|t a \TeX|
|00001d60| 7b 7d 20 6d 61 63 72 6f | 20 70 61 63 6b 61 67 65 |{} macro| package|
|00001d70| 20 0a 5c 54 72 65 65 54 | 65 58 7b 7d 20 74 68 61 | .\TreeT|eX{} tha|
|00001d80| 74 20 70 72 6f 64 75 63 | 65 73 20 61 20 64 72 61 |t produc|es a dra|
|00001d90| 77 69 6e 67 20 6f 66 20 | 61 20 74 72 65 65 20 66 |wing of |a tree f|
|00001da0| 72 6f 6d 20 61 20 70 75 | 72 65 6c 79 20 6c 6f 67 |rom a pu|rely log|
|00001db0| 69 63 61 6c 20 20 20 20 | 20 20 20 20 20 20 20 20 |ical | |
|00001dc0| 20 20 0a 64 65 73 63 72 | 69 70 74 69 6f 6e 2e 20 | .descr|iption. |
|00001dd0| 4f 75 72 20 61 70 70 72 | 6f 61 63 68 20 68 61 73 |Our appr|oach has|
|00001de0| 20 74 68 72 65 65 20 61 | 64 76 61 6e 74 61 67 65 | three a|dvantage|
|00001df0| 73 2e 20 46 69 72 73 74 | 2c 20 6c 61 62 65 6c 73 |s. First|, labels|
|00001e00| 20 20 20 20 20 20 20 20 | 20 20 20 0a 66 6f 72 20 | | .for |
|00001e10| 6e 6f 64 65 73 20 63 61 | 6e 20 62 65 20 68 61 6e |nodes ca|n be han|
|00001e20| 64 6c 65 64 20 69 6e 20 | 61 20 72 65 61 73 6f 6e |dled in |a reason|
|00001e30| 61 62 6c 65 20 77 61 79 | 2e 20 4f 6e 20 74 68 65 |able way|. On the|
|00001e40| 20 6f 6e 65 20 68 61 6e | 64 2c 20 74 68 65 20 74 | one han|d, the t|
|00001e50| 72 65 65 20 20 20 20 20 | 20 20 20 20 0a 64 72 61 |ree | .dra|
|00001e60| 77 69 6e 67 20 61 6c 67 | 6f 72 69 74 68 6d 20 63 |wing alg|orithm c|
|00001e70| 61 6e 20 63 6f 6d 70 75 | 74 65 20 74 68 65 20 77 |an compu|te the w|
|00001e80| 69 64 74 68 73 20 6f 66 | 20 74 68 65 20 6c 61 62 |idths of| the lab|
|00001e90| 65 6c 73 20 61 6e 64 20 | 74 61 6b 65 20 20 20 20 |els and |take |
|00001ea0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 74 68 | | .th|
|00001eb0| 65 6d 20 69 6e 74 6f 20 | 61 63 63 6f 75 6e 74 20 |em into |account |
|00001ec0| 66 6f 72 20 74 68 65 20 | 70 6f 73 69 74 69 6f 6e |for the |position|
|00001ed0| 69 6e 67 20 6f 66 20 74 | 68 65 20 6e 6f 64 65 73 |ing of t|he nodes|
|00001ee0| 3b 20 6f 6e 20 74 68 65 | 20 6f 74 68 65 72 20 68 |; on the| other h|
|00001ef0| 61 6e 64 2c 20 20 20 20 | 20 20 20 20 20 20 0a 61 |and, | .a|
|00001f00| 6c 6c 20 74 68 65 20 74 | 65 78 74 75 61 6c 20 70 |ll the t|extual p|
|00001f10| 61 72 74 73 20 6f 66 20 | 74 68 65 20 64 6f 63 75 |arts of |the docu|
|00001f20| 6d 65 6e 74 20 63 61 6e | 20 62 65 20 74 72 65 61 |ment can| be trea|
|00001f30| 74 65 64 20 75 6e 69 66 | 6f 72 6d 6c 79 2e 20 53 |ted unif|ormly. S|
|00001f40| 65 63 6f 6e 64 2c 20 20 | 20 20 20 20 20 20 20 0a |econd, | .|
|00001f50| 5c 54 72 65 65 54 65 58 | 7b 7d 20 63 61 6e 20 62 |\TreeTeX|{} can b|
|00001f60| 65 20 74 72 69 76 69 61 | 6c 6c 79 20 70 6f 72 74 |e trivia|lly port|
|00001f70| 65 64 20 74 6f 20 61 6e | 79 20 73 69 74 65 20 72 |ed to an|y site r|
|00001f80| 75 6e 6e 69 6e 67 20 5c | 54 65 58 7b 7d 2e 20 46 |unning \|TeX{}. F|
|00001f90| 69 6e 61 6c 6c 79 2c 20 | 20 20 20 20 20 20 20 20 |inally, | |
|00001fa0| 0a 6d 6f 64 75 6c 61 72 | 69 74 79 20 69 6e 20 74 |.modular|ity in t|
|00001fb0| 68 65 20 64 65 73 63 72 | 69 70 74 69 6f 6e 20 6f |he descr|iption o|
|00001fc0| 66 20 61 20 74 72 65 65 | 20 61 6e 64 20 5c 54 65 |f a tree| and \Te|
|00001fd0| 58 7b 7d 27 73 20 6d 61 | 63 72 6f 20 63 61 70 61 |X{}'s ma|cro capa|
|00001fe0| 62 69 6c 69 74 69 65 73 | 20 20 20 20 20 20 20 20 |bilities| |
|00001ff0| 20 0a 61 6c 6c 6f 77 20 | 66 6f 72 20 6c 69 62 72 | .allow |for libr|
|00002000| 61 72 69 65 73 20 6f 66 | 20 73 75 62 74 72 65 65 |aries of| subtree|
|00002010| 73 20 61 6e 64 20 74 72 | 65 65 20 63 6c 61 73 73 |s and tr|ee class|
|00002020| 65 73 2e 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |es. | |
|00002030| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002040| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00002050| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002080| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002090| 20 20 20 0a 49 6e 20 61 | 64 64 69 74 69 6f 6e 2c | .In a|ddition,|
|000020a0| 20 77 65 20 68 61 76 65 | 20 69 6d 70 6c 65 6d 65 | we have| impleme|
|000020b0| 6e 74 65 64 20 61 6e 20 | 6f 70 74 69 6f 6e 20 74 |nted an |option t|
|000020c0| 68 61 74 20 70 72 6f 64 | 75 63 65 73 20 20 20 20 |hat prod|uces |
|000020d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000020e0| 20 20 20 20 0a 64 72 61 | 77 69 6e 67 73 20 77 68 | .dra|wings wh|
|000020f0| 69 63 68 20 6d 61 6b 65 | 20 74 68 65 20 20 20 20 |ich make| the |
|00002100| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002110| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002120| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002130| 20 20 20 20 20 0a 5c 65 | 6d 70 68 7b 73 74 72 75 | .\e|mph{stru|
|00002140| 63 74 75 72 65 7d 20 6f | 66 20 74 68 65 20 74 72 |cture} o|f the tr|
|00002150| 65 65 73 20 6d 6f 72 65 | 20 6f 62 76 69 6f 75 73 |ees more| obvious|
|00002160| 20 74 6f 20 74 68 65 20 | 68 75 6d 61 6e 20 65 79 | to the |human ey|
|00002170| 65 2c 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e, | |
|00002180| 20 20 20 20 20 20 0a 65 | 76 65 6e 20 74 68 6f 75 | .e|ven thou|
|00002190| 67 68 20 74 68 65 79 20 | 6d 61 79 20 6e 6f 74 20 |gh they |may not |
|000021a0| 62 65 20 61 73 20 61 65 | 73 74 68 65 74 69 63 61 |be as ae|sthetica|
|000021b0| 6c 6c 79 20 70 6c 65 61 | 73 69 6e 67 2e 20 20 20 |lly plea|sing. |
|000021c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000021d0| 20 20 20 20 20 20 20 0a | 20 20 20 20 20 20 20 20 | .| |
|000021e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000021f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002200| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002210| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002220| 20 20 20 20 20 20 20 20 | 0a 5c 65 6e 64 7b 61 62 | |.\end{ab|
|00002230| 73 74 72 61 63 74 7d 20 | 20 20 20 20 20 20 20 20 |stract} | |
|00002240| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002250| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002260| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002270| 20 20 20 20 20 20 20 20 | 20 0a 20 20 20 20 20 20 | | . |
|00002280| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002290| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000022a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000022b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000022c0| 20 20 20 20 20 20 20 20 | 20 20 0a 5c 73 65 63 74 | | .\sect|
|000022d0| 69 6f 6e 7b 41 65 73 74 | 68 65 74 69 63 61 6c 20 |ion{Aest|hetical |
|000022e0| 63 72 69 74 65 72 69 61 | 20 66 6f 72 20 64 72 61 |criteria| for dra|
|000022f0| 77 69 6e 67 20 74 72 65 | 65 73 7d 20 20 20 20 20 |wing tre|es} |
|00002300| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002310| 20 20 20 20 20 20 20 20 | 20 20 20 0a 20 20 20 20 | | . |
|00002320| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002330| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002340| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002350| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002360| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 4f 6e 65 | | .One|
|00002370| 20 6f 66 20 74 68 65 20 | 6d 6f 73 74 20 63 6f 6d | of the |most com|
|00002380| 6d 6f 6e 6c 79 20 75 73 | 65 64 20 64 61 74 61 20 |monly us|ed data |
|00002390| 73 74 72 75 63 74 75 72 | 65 73 20 69 6e 20 63 6f |structur|es in co|
|000023a0| 6d 70 75 74 65 72 20 73 | 63 69 65 6e 63 65 20 69 |mputer s|cience i|
|000023b0| 73 20 74 68 65 20 74 72 | 65 65 2e 20 20 0a 41 73 |s the tr|ee. .As|
|000023c0| 20 6d 61 6e 79 20 70 65 | 6f 70 6c 65 20 61 72 65 | many pe|ople are|
|000023d0| 20 75 73 69 6e 67 20 74 | 72 65 65 73 20 69 6e 20 | using t|rees in |
|000023e0| 74 68 65 69 72 20 72 65 | 73 65 61 72 63 68 20 6f |their re|search o|
|000023f0| 72 20 6a 75 73 74 20 61 | 73 20 69 6c 6c 75 73 74 |r just a|s illust|
|00002400| 72 61 74 69 6f 6e 20 20 | 20 20 20 20 20 20 0a 74 |ration | .t|
|00002410| 6f 6f 6c 73 2c 20 74 68 | 65 79 20 61 72 65 20 75 |ools, th|ey are u|
|00002420| 73 75 61 6c 6c 79 20 73 | 74 72 75 67 67 6c 69 6e |sually s|trugglin|
|00002430| 67 20 77 69 74 68 20 74 | 68 65 20 70 72 6f 62 6c |g with t|he probl|
|00002440| 65 6d 20 6f 66 20 20 20 | 20 20 20 20 20 20 20 20 |em of | |
|00002450| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00002460| 5c 65 6d 70 68 7b 64 72 | 61 77 69 6e 67 7d 20 74 |\emph{dr|awing} t|
|00002470| 72 65 65 73 2e 20 57 65 | 20 61 72 65 20 63 6f 6e |rees. We| are con|
|00002480| 63 65 72 6e 65 64 20 70 | 72 69 6d 61 72 69 6c 79 |cerned p|rimarily|
|00002490| 20 77 69 74 68 20 6f 72 | 64 65 72 65 64 20 20 20 | with or|dered |
|000024a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000024b0| 0a 74 72 65 65 73 20 69 | 6e 20 74 68 65 20 73 65 |.trees i|n the se|
|000024c0| 6e 73 65 20 6f 66 7e 5c | 63 69 74 65 7b 41 43 50 |nse of~\|cite{ACP|
|000024d0| 7d 2c 20 65 73 70 65 63 | 69 61 6c 6c 79 20 62 69 |}, espec|ially bi|
|000024e0| 6e 61 72 79 20 61 6e 64 | 20 75 6e 61 72 79 2d 62 |nary and| unary-b|
|000024f0| 69 6e 61 72 79 20 20 20 | 20 20 20 20 20 20 20 20 |inary | |
|00002500| 20 0a 74 72 65 65 73 2e | 20 41 20 62 69 6e 61 72 | .trees.| A binar|
|00002510| 79 20 74 72 65 65 20 69 | 73 20 61 20 66 69 6e 69 |y tree i|s a fini|
|00002520| 74 65 20 73 65 74 20 6f | 66 20 6e 6f 64 65 73 20 |te set o|f nodes |
|00002530| 77 68 69 63 68 20 65 69 | 74 68 65 72 20 20 20 20 |which ei|ther |
|00002540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002550| 20 20 0a 69 73 20 65 6d | 70 74 79 2c 20 6f 72 20 | .is em|pty, or |
|00002560| 63 6f 6e 73 69 73 74 73 | 20 6f 66 20 61 20 72 6f |consists| of a ro|
|00002570| 6f 74 20 61 6e 64 20 74 | 77 6f 20 64 69 73 6a 6f |ot and t|wo disjo|
|00002580| 69 6e 74 20 62 69 6e 61 | 72 79 20 74 72 65 65 73 |int bina|ry trees|
|00002590| 20 63 61 6c 6c 65 64 20 | 20 20 20 20 20 20 20 20 | called | |
|000025a0| 20 20 20 0a 74 68 65 20 | 6c 65 66 74 20 61 6e 64 | .the |left and|
|000025b0| 20 72 69 67 68 74 20 73 | 75 62 74 72 65 65 73 20 | right s|ubtrees |
|000025c0| 6f 66 20 74 68 65 20 72 | 6f 6f 74 2e 20 41 20 75 |of the r|oot. A u|
|000025d0| 6e 61 72 79 2d 62 69 6e | 61 72 79 20 74 72 65 65 |nary-bin|ary tree|
|000025e0| 20 69 73 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | is | |
|000025f0| 20 20 20 20 0a 61 20 66 | 69 6e 69 74 65 20 73 65 | .a f|inite se|
|00002600| 74 20 6f 66 20 6e 6f 64 | 65 73 20 77 68 69 63 68 |t of nod|es which|
|00002610| 20 65 69 74 68 65 72 20 | 69 73 20 65 6d 70 74 79 | either |is empty|
|00002620| 2c 20 6f 72 20 63 6f 6e | 73 69 73 74 73 20 6f 66 |, or con|sists of|
|00002630| 20 61 20 72 6f 6f 74 20 | 61 6e 64 20 20 20 20 20 | a root |and |
|00002640| 20 20 20 20 20 0a 74 77 | 6f 20 64 69 73 6a 6f 69 | .tw|o disjoi|
|00002650| 6e 74 20 75 6e 61 72 79 | 2d 62 69 6e 61 72 79 20 |nt unary|-binary |
|00002660| 74 72 65 65 73 2c 20 6f | 72 20 63 6f 6e 73 69 73 |trees, o|r consis|
|00002670| 74 73 20 6f 66 20 61 20 | 72 6f 6f 74 20 61 6e 64 |ts of a |root and|
|00002680| 20 6f 6e 65 20 20 20 20 | 20 20 20 20 20 20 20 20 | one | |
|00002690| 20 20 20 20 20 20 0a 6e | 6f 6e 65 6d 70 74 79 20 | .n|onempty |
|000026a0| 75 6e 61 72 79 2d 62 69 | 6e 61 72 79 20 74 72 65 |unary-bi|nary tre|
|000026b0| 65 2e 20 41 6e 20 65 78 | 74 65 6e 64 65 64 20 62 |e. An ex|tended b|
|000026c0| 69 6e 61 72 79 20 74 72 | 65 65 20 69 73 20 61 20 |inary tr|ee is a |
|000026d0| 62 69 6e 61 72 79 20 74 | 72 65 65 20 20 20 20 20 |binary t|ree |
|000026e0| 20 20 20 20 20 20 20 0a | 69 6e 20 77 68 69 63 68 | .|in which|
|000026f0| 20 65 61 63 68 20 6e 6f | 64 65 20 68 61 73 20 65 | each no|de has e|
|00002700| 69 74 68 65 72 20 74 77 | 6f 20 6e 6f 6e 65 6d 70 |ither tw|o nonemp|
|00002710| 74 79 20 73 75 62 74 72 | 65 65 73 20 6f 72 20 74 |ty subtr|ees or t|
|00002720| 77 6f 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |wo | |
|00002730| 20 20 20 20 20 20 20 20 | 0a 65 6d 70 74 79 20 73 | |.empty s|
|00002740| 75 62 74 72 65 65 73 2e | 20 20 20 20 20 20 20 20 |ubtrees.| |
|00002750| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002760| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002770| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002780| 20 20 20 20 20 20 20 20 | 20 0a 20 20 20 20 20 20 | | . |
|00002790| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000027a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000027b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000027c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000027d0| 20 20 20 20 20 20 20 20 | 20 20 0a 46 6f 72 20 74 | | .For t|
|000027e0| 68 65 73 65 20 74 72 65 | 65 73 20 74 68 65 72 65 |hese tre|es there|
|000027f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002800| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002810| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002820| 20 20 20 20 20 20 20 20 | 20 20 20 0a 61 72 65 20 | | .are |
|00002830| 73 6f 6d 65 20 62 61 73 | 69 63 20 61 67 72 65 65 |some bas|ic agree|
|00002840| 6d 65 6e 74 73 20 6f 6e | 20 68 6f 77 20 74 68 65 |ments on| how the|
|00002850| 79 20 73 68 6f 75 6c 64 | 20 62 65 20 64 72 61 77 |y should| be draw|
|00002860| 6e 2c 20 72 65 66 6c 65 | 63 74 69 6e 67 20 20 20 |n, refle|cting |
|00002870| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 74 68 65 | | .the|
|00002880| 20 74 6f 70 2d 64 6f 77 | 6e 20 61 6e 64 20 6c 65 | top-dow|n and le|
|00002890| 66 74 2d 72 69 67 68 74 | 20 6f 72 64 65 72 69 6e |ft-right| orderin|
|000028a0| 67 20 6f 66 20 6e 6f 64 | 65 73 20 69 6e 20 61 20 |g of nod|es in a |
|000028b0| 74 72 65 65 3b 20 20 20 | 20 20 20 20 20 20 20 20 |tree; | |
|000028c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 73 65 | | .se|
|000028d0| 65 20 5c 63 69 74 65 7b | 54 69 64 69 65 72 54 72 |e \cite{|TidierTr|
|000028e0| 65 65 73 7d 20 61 6e 64 | 20 5c 63 69 74 65 7b 54 |ees} and| \cite{T|
|000028f0| 69 64 79 54 72 65 65 73 | 7d 2e 20 20 20 20 20 20 |idyTrees|}. |
|00002900| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002910| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 20 | | . |
|00002920| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002930| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002940| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002950| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002960| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00002970| 5c 62 65 67 69 6e 7b 65 | 6e 75 6d 65 72 61 74 65 |\begin{e|numerate|
|00002980| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|00002990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000029a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000029b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000029c0| 0a 5c 69 74 65 6d 5b 31 | 2e 5d 20 54 72 65 65 73 |.\item[1|.] Trees|
|000029d0| 20 69 6d 70 6f 73 65 20 | 61 20 64 69 73 74 61 6e | impose |a distan|
|000029e0| 63 65 20 6f 6e 20 74 68 | 65 20 6e 6f 64 65 73 3b |ce on th|e nodes;|
|000029f0| 20 6e 6f 20 6e 6f 64 65 | 20 20 20 20 20 20 20 20 | no node| |
|00002a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002a10| 20 0a 20 20 20 20 20 20 | 20 20 20 20 73 68 6f 75 | . | shou|
|00002a20| 6c 64 20 62 65 20 63 6c | 6f 73 65 72 20 74 6f 20 |ld be cl|oser to |
|00002a30| 74 68 65 20 72 6f 6f 74 | 20 74 68 61 6e 20 61 6e |the root| than an|
|00002a40| 79 20 6f 66 20 69 74 73 | 20 20 20 20 20 20 20 20 |y of its| |
|00002a50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002a60| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 61 6e 63 | . | anc|
|00002a70| 65 73 74 6f 72 73 2e 20 | 20 20 20 20 20 20 20 20 |estors. | |
|00002a80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002a90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002aa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002ab0| 20 20 20 0a 5c 69 74 65 | 6d 5b 32 2e 5d 20 4e 6f | .\ite|m[2.] No|
|00002ac0| 64 65 73 20 6f 66 20 61 | 20 74 72 65 65 20 61 74 |des of a| tree at|
|00002ad0| 20 74 68 65 20 73 61 6d | 65 20 68 65 69 67 68 74 | the sam|e height|
|00002ae0| 20 73 68 6f 75 6c 64 20 | 6c 69 65 20 6f 6e 20 61 | should |lie on a|
|00002af0| 20 73 74 72 61 69 67 68 | 74 20 20 20 20 20 20 20 | straigh|t |
|00002b00| 20 20 20 20 0a 20 20 20 | 20 20 20 20 20 20 20 6c | . | l|
|00002b10| 69 6e 65 2c 20 61 6e 64 | 20 74 68 65 20 73 74 72 |ine, and| the str|
|00002b20| 61 69 67 68 74 20 6c 69 | 6e 65 73 20 64 65 66 69 |aight li|nes defi|
|00002b30| 6e 69 6e 67 20 74 68 65 | 20 6c 65 76 65 6c 73 20 |ning the| levels |
|00002b40| 73 68 6f 75 6c 64 20 62 | 65 20 20 20 20 20 20 20 |should b|e |
|00002b50| 20 20 20 20 20 0a 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00002b60| 70 61 72 61 6c 6c 65 6c | 2e 20 20 20 20 20 20 20 |parallel|. |
|00002b70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002b80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002b90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002ba0| 20 20 20 20 20 20 0a 5c | 69 74 65 6d 5b 33 2e 5d | .\|item[3.]|
|00002bb0| 20 54 68 65 20 72 65 6c | 61 74 69 76 65 20 6f 72 | The rel|ative or|
|00002bc0| 64 65 72 20 6f 66 20 6e | 6f 64 65 73 20 6f 6e 20 |der of n|odes on |
|00002bd0| 61 6e 79 20 6c 65 76 65 | 6c 20 73 68 6f 75 6c 64 |any leve|l should|
|00002be0| 20 62 65 20 74 68 65 20 | 73 61 6d 65 20 20 20 20 | be the |same |
|00002bf0| 20 20 20 20 20 20 20 0a | 20 20 20 20 20 20 20 20 | .| |
|00002c00| 20 20 61 73 20 69 6e 20 | 74 68 65 20 6c 65 76 65 | as in |the leve|
|00002c10| 6c 20 6f 72 64 65 72 20 | 74 72 61 76 65 72 73 61 |l order |traversa|
|00002c20| 6c 20 6f 66 20 74 68 65 | 20 74 72 65 65 2e 20 20 |l of the| tree. |
|00002c30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002c40| 20 20 20 20 20 20 20 20 | 0a 5c 65 6e 64 7b 65 6e | |.\end{en|
|00002c50| 75 6d 65 72 61 74 65 7d | 20 20 20 20 20 20 20 20 |umerate}| |
|00002c60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002c70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002c80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002c90| 20 20 20 20 20 20 20 20 | 20 0a 20 20 20 20 20 20 | | . |
|00002ca0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002cb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002cd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002ce0| 20 20 20 20 20 20 20 20 | 20 20 0a 54 68 65 73 65 | | .These|
|00002cf0| 20 61 78 69 6f 6d 73 20 | 67 75 61 72 61 6e 74 65 | axioms |guarante|
|00002d00| 65 20 74 68 61 74 20 74 | 72 65 65 73 20 61 72 65 |e that t|rees are|
|00002d10| 20 64 72 61 77 6e 20 61 | 73 20 70 6c 61 6e 61 72 | drawn a|s planar|
|00002d20| 20 67 72 61 70 68 73 3a | 20 65 64 67 65 73 20 64 | graphs:| edges d|
|00002d30| 6f 20 20 20 20 20 20 20 | 20 20 20 0a 6e 6f 74 20 |o | .not |
|00002d40| 69 6e 74 65 72 73 65 63 | 74 20 65 78 63 65 70 74 |intersec|t except|
|00002d50| 20 61 74 20 6e 6f 64 65 | 73 2e 20 54 77 6f 20 66 | at node|s. Two f|
|00002d60| 75 72 74 68 65 72 20 61 | 78 69 6f 6d 73 20 69 6d |urther a|xioms im|
|00002d70| 70 72 6f 76 65 20 74 68 | 65 20 61 65 73 74 68 65 |prove th|e aesthe|
|00002d80| 74 69 63 61 6c 20 20 20 | 20 20 20 20 0a 61 70 70 |tical | .app|
|00002d90| 65 61 72 61 6e 63 65 20 | 6f 66 20 74 72 65 65 73 |earance |of trees|
|00002da0| 3a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |: | |
|00002db0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 | | . |
|00002de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 5c | | .\|
|00002e30| 62 65 67 69 6e 7b 65 6e | 75 6d 65 72 61 74 65 7d |begin{en|umerate}|
|00002e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002e70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00002e80| 5c 69 74 65 6d 5b 34 2e | 5d 20 49 6e 20 61 20 75 |\item[4.|] In a u|
|00002e90| 6e 61 72 79 2d 62 69 6e | 61 72 79 20 74 72 65 65 |nary-bin|ary tree|
|00002ea0| 2c 20 65 61 63 68 20 6c | 65 66 74 20 63 68 69 6c |, each l|eft chil|
|00002eb0| 64 20 73 68 6f 75 6c 64 | 20 62 65 20 70 6f 73 69 |d should| be posi|
|00002ec0| 74 69 6f 6e 65 64 20 20 | 20 20 20 20 20 20 20 20 |tioned | |
|00002ed0| 0a 20 20 20 20 20 20 20 | 20 20 20 74 6f 20 74 68 |. | to th|
|00002ee0| 65 20 6c 65 66 74 20 6f | 66 20 69 74 73 20 70 61 |e left o|f its pa|
|00002ef0| 72 65 6e 74 2c 20 65 61 | 63 68 20 20 20 20 20 20 |rent, ea|ch |
|00002f00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002f10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002f20| 20 0a 20 20 20 20 20 20 | 20 20 20 20 72 69 67 68 | . | righ|
|00002f30| 74 20 63 68 69 6c 64 20 | 74 6f 20 74 68 65 20 72 |t child |to the r|
|00002f40| 69 67 68 74 20 6f 66 20 | 69 74 73 20 70 61 72 65 |ight of |its pare|
|00002f50| 6e 74 2c 20 61 6e 64 20 | 65 61 63 68 20 75 6e 61 |nt, and |each una|
|00002f60| 72 79 20 63 68 69 6c 64 | 20 20 20 20 20 20 20 20 |ry child| |
|00002f70| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 73 68 6f | . | sho|
|00002f80| 75 6c 64 20 62 65 20 70 | 6f 73 69 74 69 6f 6e 65 |uld be p|ositione|
|00002f90| 64 20 62 65 6c 6f 77 20 | 69 74 73 20 70 61 72 65 |d below |its pare|
|00002fa0| 6e 74 2e 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |nt. | |
|00002fb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00002fc0| 20 20 20 0a 5c 69 74 65 | 6d 5b 35 2e 5d 20 41 20 | .\ite|m[5.] A |
|00002fd0| 70 61 72 65 6e 74 20 73 | 68 6f 75 6c 64 20 62 65 |parent s|hould be|
|00002fe0| 20 63 65 6e 74 65 72 65 | 64 20 6f 76 65 72 20 69 | centere|d over i|
|00002ff0| 74 73 20 63 68 69 6c 64 | 72 65 6e 2e 20 20 20 20 |ts child|ren. |
|00003000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003010| 20 20 20 20 0a 5c 65 6e | 64 7b 65 6e 75 6d 65 72 | .\en|d{enumer|
|00003020| 61 74 65 7d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ate} | |
|00003030| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003040| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003050| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003060| 20 20 20 20 20 0a 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00003070| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003080| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003090| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000030a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000030b0| 20 20 20 20 20 20 0a 41 | 6e 20 61 64 64 69 74 69 | .A|n additi|
|000030c0| 6f 6e 61 6c 20 61 78 69 | 6f 6d 20 64 65 61 6c 73 |onal axi|om deals|
|000030d0| 20 77 69 74 68 20 74 68 | 65 20 70 72 6f 62 6c 65 | with th|e proble|
|000030e0| 6d 20 6f 66 20 74 72 65 | 65 20 64 72 61 77 69 6e |m of tre|e drawin|
|000030f0| 67 73 20 62 65 63 6f 6d | 69 6e 67 20 74 6f 6f 20 |gs becom|ing too |
|00003100| 77 69 64 65 20 20 20 0a | 61 6e 64 20 74 68 65 72 |wide .|and ther|
|00003110| 65 66 6f 72 65 20 65 78 | 63 65 65 64 69 6e 67 20 |efore ex|ceeding |
|00003120| 74 68 65 20 70 68 79 73 | 69 63 61 6c 20 6c 69 6d |the phys|ical lim|
|00003130| 69 74 20 6f 66 20 74 68 | 65 20 6f 75 74 70 75 74 |it of th|e output|
|00003140| 20 6d 65 64 69 75 6d 3a | 20 20 20 20 20 20 20 20 | medium:| |
|00003150| 20 20 20 20 20 20 20 20 | 0a 20 20 20 20 20 20 20 | |. |
|00003160| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003170| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000031a0| 20 20 20 20 20 20 20 20 | 20 0a 5c 62 65 67 69 6e | | .\begin|
|000031b0| 7b 65 6e 75 6d 65 72 61 | 74 65 7d 20 20 20 20 20 |{enumera|te} |
|000031c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000031d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000031e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000031f0| 20 20 20 20 20 20 20 20 | 20 20 0a 5c 69 74 65 6d | | .\item|
|00003200| 5b 36 2e 5d 20 54 72 65 | 65 20 64 72 61 77 69 6e |[6.] Tre|e drawin|
|00003210| 67 73 20 73 68 6f 75 6c | 64 20 6f 63 63 75 70 79 |gs shoul|d occupy|
|00003220| 20 61 73 20 6c 69 74 74 | 6c 65 20 77 69 64 74 68 | as litt|le width|
|00003230| 20 61 73 20 70 6f 73 73 | 69 62 6c 65 20 77 69 74 | as poss|ible wit|
|00003240| 68 6f 75 74 20 20 20 20 | 20 20 20 0a 20 20 20 20 |hout | . |
|00003250| 20 20 20 20 20 20 76 69 | 6f 6c 61 74 69 6e 67 20 | vi|olating |
|00003260| 74 68 65 20 6f 74 68 65 | 72 20 61 78 69 6f 6d 73 |the othe|r axioms|
|00003270| 2e 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00003280| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003290| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 65 6e | | .\en|
|000032a0| 64 7b 65 6e 75 6d 65 72 | 61 74 65 7d 20 20 20 20 |d{enumer|ate} |
|000032b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000032c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000032d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000032e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 | | . |
|000032f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003300| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003310| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003320| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003330| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 49 | | .I|
|00003340| 6e 20 5c 63 69 74 65 7b | 54 69 64 79 54 72 65 65 |n \cite{|TidyTree|
|00003350| 73 7d 2c 20 57 65 74 68 | 65 72 65 6c 6c 20 61 6e |s}, Weth|erell an|
|00003360| 64 20 53 68 61 6e 6e 6f | 6e 20 69 6e 74 72 6f 64 |d Shanno|n introd|
|00003370| 75 63 65 20 74 77 6f 20 | 61 6c 67 6f 72 69 74 68 |uce two |algorith|
|00003380| 6d 73 20 66 6f 72 20 20 | 20 20 20 20 20 20 20 0a |ms for | .|
|00003390| 74 72 65 65 20 64 72 61 | 77 69 6e 67 73 2c 20 74 |tree dra|wings, t|
|000033a0| 68 65 20 66 69 72 73 74 | 20 6f 66 20 77 68 69 63 |he first| of whic|
|000033b0| 68 20 66 75 6c 66 69 6c | 6c 73 20 61 78 69 6f 6d |h fulfil|ls axiom|
|000033c0| 73 7e 31 2d 2d 35 2c 20 | 61 6e 64 20 74 68 65 20 |s~1--5, |and the |
|000033d0| 73 65 63 6f 6e 64 20 20 | 20 20 20 20 20 20 20 20 |second | |
|000033e0| 0a 31 2d 2d 36 2e 20 48 | 6f 77 65 76 65 72 2c 20 |.1--6. H|owever, |
|000033f0| 61 73 20 52 65 69 6e 67 | 6f 6c 64 20 61 6e 64 20 |as Reing|old and |
|00003400| 54 69 6c 66 6f 72 64 20 | 69 6e 20 5c 63 69 74 65 |Tilford |in \cite|
|00003410| 7b 54 69 64 69 65 72 54 | 72 65 65 73 7d 20 20 20 |{TidierT|rees} |
|00003420| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003430| 20 0a 70 6f 69 6e 74 20 | 6f 75 74 2c 20 74 68 65 | .point |out, the|
|00003440| 72 65 20 69 73 20 61 20 | 6c 61 63 6b 20 6f 66 20 |re is a |lack of |
|00003450| 73 79 6d 6d 65 74 72 79 | 20 69 6e 20 74 68 65 20 |symmetry| in the |
|00003460| 61 6c 67 6f 72 69 74 68 | 6d 73 20 6f 66 20 20 20 |algorith|ms of |
|00003470| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003480| 20 20 0a 57 65 74 68 65 | 72 65 6c 6c 20 61 6e 64 | .Wethe|rell and|
|00003490| 20 53 68 61 6e 6e 6f 6e | 20 77 68 69 63 68 20 6d | Shannon| which m|
|000034a0| 61 79 20 6c 65 61 64 20 | 74 6f 20 75 6e 70 6c 65 |ay lead |to unple|
|000034b0| 61 73 61 6e 74 20 72 65 | 73 75 6c 74 73 2e 0a 54 |asant re|sults..T|
|000034c0| 68 65 72 65 66 6f 72 65 | 2c 20 52 65 69 6e 67 6f |herefore|, Reingo|
|000034d0| 6c 64 20 61 6e 64 20 54 | 69 6c 66 6f 72 64 20 69 |ld and T|ilford i|
|000034e0| 6e 74 72 6f 64 75 63 65 | 20 61 20 6e 65 77 20 73 |ntroduce| a new s|
|000034f0| 74 72 75 63 74 75 72 65 | 64 20 20 20 20 20 20 20 |tructure|d |
|00003500| 20 0a 61 78 69 6f 6d 3a | 20 20 20 20 20 20 20 20 | .axiom:| |
|00003510| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003520| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003530| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003550| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00003560| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003570| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003580| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003590| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000035a0| 20 20 20 0a 5c 62 65 67 | 69 6e 7b 65 6e 75 6d 65 | .\beg|in{enume|
|000035b0| 72 61 74 65 7d 20 20 20 | 20 20 20 20 20 20 20 20 |rate} | |
|000035c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000035d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000035e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000035f0| 20 20 20 20 0a 5c 69 74 | 65 6d 5b 37 2e 5d 20 41 | .\it|em[7.] A|
|00003600| 20 73 75 62 74 72 65 65 | 20 6f 66 20 61 20 67 69 | subtree| of a gi|
|00003610| 76 65 6e 20 74 72 65 65 | 20 73 68 6f 75 6c 64 20 |ven tree| should |
|00003620| 62 65 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |be | |
|00003630| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003640| 20 20 20 20 20 0a 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00003650| 64 72 61 77 6e 20 74 68 | 65 20 73 61 6d 65 20 77 |drawn th|e same w|
|00003660| 61 79 20 72 65 67 61 72 | 64 6c 65 73 73 20 6f 66 |ay regar|dless of|
|00003670| 20 77 68 65 72 65 20 69 | 74 20 6f 63 63 75 72 73 | where i|t occurs|
|00003680| 20 69 6e 20 74 68 65 20 | 67 69 76 65 6e 20 74 72 | in the |given tr|
|00003690| 65 65 2e 20 20 20 0a 5c | 65 6e 64 7b 65 6e 75 6d |ee. .\|end{enum|
|000036a0| 65 72 61 74 65 7d 20 20 | 20 20 20 20 20 20 20 20 |erate} | |
|000036b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000036c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000036d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000036e0| 20 20 20 20 20 20 20 0a | 20 20 20 20 20 20 20 20 | .| |
|000036f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003700| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003710| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003720| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003730| 20 20 20 20 20 20 20 20 | 0a 41 78 69 6f 6d 7e 37 | |.Axiom~7|
|00003740| 20 61 6c 6c 6f 77 73 20 | 74 68 65 20 73 61 6d 65 | allows |the same|
|00003750| 20 74 72 65 65 20 74 6f | 20 62 65 20 64 72 61 77 | tree to| be draw|
|00003760| 6e 20 64 69 66 66 65 72 | 65 6e 74 6c 79 20 77 68 |n differ|ently wh|
|00003770| 65 6e 20 69 74 20 6f 63 | 63 75 72 73 20 61 73 20 |en it oc|curs as |
|00003780| 20 20 20 20 20 20 20 20 | 20 0a 61 20 73 75 62 74 | | .a subt|
|00003790| 72 65 65 20 69 6e 20 64 | 69 66 66 65 72 65 6e 74 |ree in d|ifferent|
|000037a0| 20 74 72 65 65 73 2e 20 | 20 20 20 20 20 20 20 20 | trees. | |
|000037b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000037c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000037d0| 20 20 20 20 20 20 20 20 | 20 20 0a 52 65 69 6e 67 | | .Reing|
|000037e0| 6f 6c 64 20 61 6e 64 20 | 54 69 6c 66 6f 72 64 20 |old and |Tilford |
|000037f0| 67 69 76 65 20 61 6e 20 | 61 6c 67 6f 72 69 74 68 |give an |algorith|
|00003800| 6d 20 77 68 69 63 68 20 | 66 75 6c 66 69 6c 6c 73 |m which |fulfills|
|00003810| 20 61 78 69 6f 6d 73 7e | 31 2d 2d 35 20 20 20 20 | axioms~|1--5 |
|00003820| 20 20 20 20 20 20 20 20 | 20 20 20 0a 61 6e 64 7e | | .and~|
|00003830| 37 2e 20 41 6c 74 68 6f | 75 67 68 20 20 20 20 20 |7. Altho|ugh |
|00003840| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003850| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003860| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003870| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 74 68 69 | | .thi|
|00003880| 73 20 61 6c 67 6f 72 69 | 74 68 6d 20 64 6f 65 73 |s algori|thm does|
|00003890| 6e 27 74 20 66 75 6c 66 | 69 6c 6c 20 61 78 69 6f |n't fulf|ill axio|
|000038a0| 6d 7e 36 2c 20 20 20 20 | 20 20 0a 74 68 65 20 61 |m~6, | .the a|
|000038b0| 65 73 74 68 65 74 69 63 | 61 6c 20 69 6d 70 72 6f |esthetic|al impro|
|000038c0| 76 65 6d 65 6e 74 73 20 | 61 72 65 20 77 65 6c 6c |vements |are well|
|000038d0| 20 77 6f 72 74 68 20 74 | 68 65 20 61 64 64 69 74 | worth t|he addit|
|000038e0| 69 6f 6e 61 6c 20 73 70 | 61 63 65 2e 0a 5c 66 69 |ional sp|ace..\fi|
|000038f0| 67 7b 61 6c 67 6f 72 69 | 74 68 6d 73 7d 20 69 6c |g{algori|thms} il|
|00003900| 6c 75 73 74 72 61 74 65 | 73 20 74 68 65 20 62 65 |lustrate|s the be|
|00003910| 6e 65 66 69 74 73 20 6f | 66 20 61 78 69 6f 6d 7e |nefits o|f axiom~|
|00003920| 37 2c 20 61 6e 64 20 5c | 66 69 67 7b 6e 61 72 72 |7, and \|fig{narr|
|00003930| 6f 77 74 72 65 65 73 7d | 0a 73 68 6f 77 73 20 74 |owtrees}|.shows t|
|00003940| 68 61 74 20 74 68 65 20 | 61 6c 67 6f 72 69 74 68 |hat the |algorith|
|00003950| 6d 20 6f 66 20 52 65 69 | 6e 67 6f 6c 64 20 61 6e |m of Rei|ngold an|
|00003960| 64 20 54 69 6c 66 6f 72 | 64 20 76 69 6f 6c 61 74 |d Tilfor|d violat|
|00003970| 65 73 20 61 78 69 6f 6d | 7e 36 2e 0a 0a 5c 62 65 |es axiom|~6...\be|
|00003980| 67 69 6e 7b 46 69 67 75 | 72 65 7d 20 20 20 20 20 |gin{Figu|re} |
|00003990| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000039a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000039b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000039c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 5c 63 | | .\c|
|000039d0| 65 6e 74 65 72 69 6e 67 | 0a 5c 6c 65 61 76 65 76 |entering|.\leavev|
|000039e0| 6d 6f 64 65 5c 6e 6f 69 | 6e 64 65 6e 74 20 20 20 |mode\noi|ndent |
|000039f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003a10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003a20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003a30| 20 20 20 0a 5c 62 65 67 | 69 6e 7b 54 72 65 65 7d | .\beg|in{Tree}|
|00003a40| 0a 5c 65 6e 6f 64 65 0a | 5c 65 6e 6f 64 65 5c 65 |.\enode.|\enode\e|
|00003a50| 6e 6f 64 65 5c 69 6e 6f | 64 65 5c 65 6e 6f 64 65 |node\ino|de\enode|
|00003a60| 5c 65 6e 6f 64 65 5c 69 | 6e 6f 64 65 5c 69 6e 6f |\enode\i|node\ino|
|00003a70| 64 65 5c 69 6e 6f 64 65 | 0a 5c 6e 6f 64 65 7b 5c |de\inode|.\node{\|
|00003a80| 65 78 74 65 72 6e 61 6c | 5c 74 79 70 65 7b 64 6f |external|\type{do|
|00003a90| 74 7d 5c 72 67 68 74 7b | 5c 75 6e 73 6b 69 70 5c |t}\rght{|\unskip\|
|00003aa0| 68 73 6b 69 70 32 5c 6d | 69 6e 73 40 70 5c 68 73 |hskip2\m|ins@p\hs|
|00003ab0| 6b 69 70 32 5c 64 6f 74 | 77 40 64 74 68 7d 7d 0a |kip2\dot|w@dth}}.|
|00003ac0| 5c 65 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 69 6e 6f |\enode\e|node\ino|
|00003ad0| 64 65 5c 65 6e 6f 64 65 | 5c 65 6e 6f 64 65 5c 69 |de\enode|\enode\i|
|00003ae0| 6e 6f 64 65 5c 69 6e 6f | 64 65 5c 69 6e 6f 64 65 |node\ino|de\inode|
|00003af0| 0a 5c 69 6e 6f 64 65 20 | 20 20 20 20 20 20 20 20 |.\inode | |
|00003b00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003b10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003b20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003b30| 20 20 20 20 20 20 20 20 | 20 20 20 0a 5c 65 6e 64 | | .\end|
|00003b40| 7b 54 72 65 65 7d 0a 5c | 68 73 6b 69 70 5c 6c 65 |{Tree}.\|hskip\le|
|00003b50| 66 74 64 69 73 74 5c 62 | 6f 78 5c 54 65 58 54 72 |ftdist\b|ox\TeXTr|
|00003b60| 65 65 5c 68 73 6b 69 70 | 5c 72 69 67 68 74 64 69 |ee\hskip|\rightdi|
|00003b70| 73 74 5c 71 71 75 61 64 | 0a 5c 62 65 67 69 6e 7b |st\qquad|.\begin{|
|00003b80| 54 72 65 65 7d 20 20 20 | 20 20 20 20 20 20 20 20 |Tree} | |
|00003b90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003ba0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003bc0| 20 20 20 20 0a 5c 65 6e | 6f 64 65 0a 5c 65 6e 6f | .\en|ode.\eno|
|00003bd0| 64 65 5c 65 6e 6f 64 65 | 5c 69 6e 6f 64 65 5c 65 |de\enode|\inode\e|
|00003be0| 6e 6f 64 65 5c 65 6e 6f | 64 65 5c 69 6e 6f 64 65 |node\eno|de\inode|
|00003bf0| 5c 69 6e 6f 64 65 5c 69 | 6e 6f 64 65 0a 5c 65 6e |\inode\i|node.\en|
|00003c00| 6f 64 65 0a 5c 65 6e 6f | 64 65 5c 65 6e 6f 64 65 |ode.\eno|de\enode|
|00003c10| 5c 69 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 65 6e 6f |\inode\e|node\eno|
|00003c20| 64 65 5c 69 6e 6f 64 65 | 5c 69 6e 6f 64 65 5c 69 |de\inode|\inode\i|
|00003c30| 6e 6f 64 65 0a 5c 69 6e | 6f 64 65 0a 5c 65 6e 64 |node.\in|ode.\end|
|00003c40| 7b 54 72 65 65 7d 0a 5c | 68 73 6b 69 70 5c 6c 65 |{Tree}.\|hskip\le|
|00003c50| 66 74 64 69 73 74 5c 62 | 6f 78 5c 54 65 58 54 72 |ftdist\b|ox\TeXTr|
|00003c60| 65 65 5c 68 73 6b 69 70 | 5c 72 69 67 68 74 64 69 |ee\hskip|\rightdi|
|00003c70| 73 74 5c 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |st\ | |
|00003c80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003c90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003ca0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003cb0| 20 20 0a 5c 63 61 70 74 | 69 6f 6e 7b 54 68 65 20 | .\capt|ion{The |
|00003cc0| 6c 65 66 74 20 74 72 65 | 65 20 69 73 20 64 72 61 |left tre|e is dra|
|00003cd0| 77 6e 20 62 79 20 74 68 | 65 20 61 6c 67 6f 72 69 |wn by th|e algori|
|00003ce0| 74 68 6d 20 6f 66 20 57 | 65 74 68 65 72 65 6c 6c |thm of W|etherell|
|00003cf0| 20 61 6e 64 20 53 68 61 | 6e 6e 6f 6e 2c 0a 61 6e | and Sha|nnon,.an|
|00003d00| 64 20 74 68 65 20 74 69 | 64 69 65 72 20 72 69 67 |d the ti|dier rig|
|00003d10| 68 74 20 6f 6e 65 20 69 | 73 20 64 72 61 77 6e 20 |ht one i|s drawn |
|00003d20| 62 79 20 74 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |by the a|lgorithm|
|00003d30| 20 6f 66 20 52 65 69 6e | 67 6f 6c 64 20 61 6e 64 | of Rein|gold and|
|00003d40| 20 54 69 6c 66 6f 72 64 | 2e 7d 20 20 20 20 20 20 | Tilford|.} |
|00003d50| 20 20 20 20 20 20 20 0a | 5c 6c 61 62 65 6c 7b 61 | .|\label{a|
|00003d60| 6c 67 6f 72 69 74 68 6d | 73 7d 20 20 20 20 20 20 |lgorithm|s} |
|00003d70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003d80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003d90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003da0| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 20 20 20 | | . |
|00003db0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003dc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003dd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 5c 76 | | .\v|
|00003e00| 73 70 61 63 65 7b 5c 66 | 69 67 73 70 61 63 65 7d |space{\f|igspace}|
|00003e10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003e30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 5c | | .\|
|00003e50| 63 65 6e 74 65 72 69 6e | 67 0a 5c 6c 65 61 76 65 |centerin|g.\leave|
|00003e60| 76 6d 6f 64 65 5c 6e 6f | 69 6e 64 65 6e 74 0a 5c |vmode\no|indent.\|
|00003e70| 62 65 67 69 6e 7b 54 72 | 65 65 7d 0a 5c 65 6e 6f |begin{Tr|ee}.\eno|
|00003e80| 64 65 5c 65 6e 6f 64 65 | 5c 65 6e 6f 64 65 5c 65 |de\enode|\enode\e|
|00003e90| 6e 6f 64 65 5c 65 6e 6f | 64 65 5c 65 6e 6f 64 65 |node\eno|de\enode|
|00003ea0| 5c 65 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 65 6e 6f |\enode\e|node\eno|
|00003eb0| 64 65 0a 5c 65 6e 6f 64 | 65 5c 69 6e 6f 64 65 5c |de.\enod|e\inode\|
|00003ec0| 69 6e 6f 64 65 5c 69 6e | 6f 64 65 20 20 20 20 20 |inode\in|ode |
|00003ed0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003ee0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003ef0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f10| 20 0a 5c 65 6e 6f 64 65 | 5c 69 6e 6f 64 65 5c 69 | .\enode|\inode\i|
|00003f20| 6e 6f 64 65 5c 69 6e 6f | 64 65 20 20 20 20 20 20 |node\ino|de |
|00003f30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003f70| 0a 5c 65 6e 6f 64 65 5c | 69 6e 6f 64 65 5c 69 6e |.\enode\|inode\in|
|00003f80| 6f 64 65 5c 69 6e 6f 64 | 65 20 20 20 20 20 20 20 |ode\inod|e |
|00003f90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003fa0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003fb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00003fc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00003fd0| 5c 65 6e 6f 64 65 5c 69 | 6e 6f 64 65 5c 69 6e 6f |\enode\i|node\ino|
|00003fe0| 64 65 5c 69 6e 6f 64 65 | 20 0a 5c 65 6e 64 7b 54 |de\inode| .\end{T|
|00003ff0| 72 65 65 7d 0a 5c 68 73 | 6b 69 70 5c 6c 65 66 74 |ree}.\hs|kip\left|
|00004000| 64 69 73 74 5c 62 6f 78 | 5c 54 65 58 54 72 65 65 |dist\box|\TeXTree|
|00004010| 5c 68 73 6b 69 70 5c 72 | 69 67 68 74 64 69 73 74 |\hskip\r|ightdist|
|00004020| 5c 71 71 75 61 64 0a 5c | 62 65 67 69 6e 7b 54 72 |\qquad.\|begin{Tr|
|00004030| 65 65 7d 0a 5c 65 6e 6f | 64 65 5c 65 6e 6f 64 65 |ee}.\eno|de\enode|
|00004040| 5c 65 6e 6f 64 65 5c 65 | 6e 6f 64 65 5c 65 6e 6f |\enode\e|node\eno|
|00004050| 64 65 5c 65 6e 6f 64 65 | 5c 65 6e 6f 64 65 5c 65 |de\enode|\enode\e|
|00004060| 6e 6f 64 65 0a 5c 6e 6f | 64 65 7b 5c 65 78 74 65 |node.\no|de{\exte|
|00004070| 72 6e 61 6c 5c 74 79 70 | 65 7b 64 6f 74 7d 5c 72 |rnal\typ|e{dot}\r|
|00004080| 67 68 74 7b 5c 75 6e 73 | 6b 69 70 5c 68 73 6b 69 |ght{\uns|kip\hski|
|00004090| 70 5c 6d 69 6e 73 40 70 | 5c 68 73 6b 69 70 5c 64 |p\mins@p|\hskip\d|
|000040a0| 6f 74 77 40 64 74 68 7d | 7d 0a 5c 65 6e 6f 64 65 |otw@dth}|}.\enode|
|000040b0| 5c 69 6e 6f 64 65 5c 69 | 6e 6f 64 65 5c 6e 6f 64 |\inode\i|node\nod|
|000040c0| 65 7b 5c 74 79 70 65 7b | 64 6f 74 7d 5c 72 67 68 |e{\type{|dot}\rgh|
|000040d0| 74 7b 5c 75 6e 73 6b 69 | 70 5c 68 73 6b 69 70 5c |t{\unski|p\hskip\|
|000040e0| 6d 69 6e 73 40 70 5c 68 | 73 6b 69 70 5c 64 6f 74 |mins@p\h|skip\dot|
|000040f0| 77 40 64 74 68 7d 7d 0a | 5c 65 6e 6f 64 65 5c 69 |w@dth}}.|\enode\i|
|00004100| 6e 6f 64 65 5c 69 6e 6f | 64 65 5c 6e 6f 64 65 7b |node\ino|de\node{|
|00004110| 5c 74 79 70 65 7b 64 6f | 74 7d 5c 72 67 68 74 7b |\type{do|t}\rght{|
|00004120| 5c 75 6e 73 6b 69 70 5c | 68 73 6b 69 70 5c 6d 69 |\unskip\|hskip\mi|
|00004130| 6e 73 40 70 5c 68 73 6b | 69 70 5c 64 6f 74 77 40 |ns@p\hsk|ip\dotw@|
|00004140| 64 74 68 7d 7d 0a 5c 65 | 6e 6f 64 65 5c 69 6e 6f |dth}}.\e|node\ino|
|00004150| 64 65 5c 69 6e 6f 64 65 | 5c 6e 6f 64 65 7b 5c 74 |de\inode|\node{\t|
|00004160| 79 70 65 7b 64 6f 74 7d | 5c 72 67 68 74 7b 5c 75 |ype{dot}|\rght{\u|
|00004170| 6e 73 6b 69 70 5c 68 73 | 6b 69 70 5c 6d 69 6e 73 |nskip\hs|kip\mins|
|00004180| 40 70 5c 68 73 6b 69 70 | 5c 64 6f 74 77 40 64 74 |@p\hskip|\dotw@dt|
|00004190| 68 7d 7d 0a 5c 65 6e 6f | 64 65 5c 69 6e 6f 64 65 |h}}.\eno|de\inode|
|000041a0| 5c 69 6e 6f 64 65 5c 69 | 6e 6f 64 65 20 0a 5c 65 |\inode\i|node .\e|
|000041b0| 6e 64 7b 54 72 65 65 7d | 0a 5c 68 73 6b 69 70 5c |nd{Tree}|.\hskip\|
|000041c0| 6c 65 66 74 64 69 73 74 | 5c 62 6f 78 5c 54 65 58 |leftdist|\box\TeX|
|000041d0| 54 72 65 65 5c 68 73 6b | 69 70 5c 72 69 67 68 74 |Tree\hsk|ip\right|
|000041e0| 64 69 73 74 5c 0a 5c 63 | 61 70 74 69 6f 6e 7b 54 |dist\.\c|aption{T|
|000041f0| 68 65 20 6c 65 66 74 20 | 74 72 65 65 20 69 73 20 |he left |tree is |
|00004200| 64 72 61 77 6e 20 62 79 | 20 74 68 65 20 61 6c 67 |drawn by| the alg|
|00004210| 6f 72 69 74 68 6d 20 6f | 66 20 52 65 69 6e 67 6f |orithm o|f Reingo|
|00004220| 6c 64 20 61 6e 64 20 54 | 69 6c 64 66 6f 72 64 2c |ld and T|ildford,|
|00004230| 20 62 75 74 0a 74 68 65 | 20 72 69 67 68 74 20 74 | but.the| right t|
|00004240| 72 65 65 20 73 68 6f 77 | 73 20 74 68 61 74 20 6e |ree show|s that n|
|00004250| 61 72 72 6f 77 65 72 20 | 64 72 61 77 69 6e 67 73 |arrower |drawings|
|00004260| 20 66 75 6c 66 69 6c 6c | 69 6e 67 20 61 6c 6c 20 | fulfill|ing all |
|00004270| 61 65 73 74 68 65 74 69 | 63 20 61 78 69 6f 6d 73 |aestheti|c axioms|
|00004280| 0a 61 72 65 20 70 6f 73 | 73 69 62 6c 65 2e 7d 0a |.are pos|sible.}.|
|00004290| 5c 6c 61 62 65 6c 7b 6e | 61 72 72 6f 77 74 72 65 |\label{n|arrowtre|
|000042a0| 65 73 7d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |es} | |
|000042b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000042c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000042d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000042e0| 20 20 20 20 20 0a 5c 65 | 6e 64 7b 46 69 67 75 72 | .\e|nd{Figur|
|000042f0| 65 7d 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e} | |
|00004300| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004310| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004320| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004330| 20 20 20 20 20 20 0a 20 | 20 20 20 20 20 20 20 20 | . | |
|00004340| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004350| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004360| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004370| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004380| 20 20 20 20 20 20 20 0a | 20 20 20 20 20 20 20 20 | .| |
|00004390| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000043a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000043b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000043c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000043d0| 20 20 20 20 20 20 20 20 | 0a 5c 73 65 63 74 69 6f | |.\sectio|
|000043e0| 6e 7b 54 68 65 20 61 6c | 67 6f 72 69 74 68 6d 20 |n{The al|gorithm |
|000043f0| 6f 66 20 52 65 69 6e 67 | 6f 6c 64 20 61 6e 64 20 |of Reing|old and |
|00004400| 54 69 6c 66 6f 72 64 7d | 20 20 20 20 20 20 20 20 |Tilford}| |
|00004410| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004420| 20 20 20 20 20 20 20 20 | 20 0a 20 20 20 20 20 20 | | . |
|00004430| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004440| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004450| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004460| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004470| 20 20 20 20 20 20 20 20 | 20 20 0a 54 68 65 20 61 | | .The a|
|00004480| 6c 67 6f 72 69 74 68 6d | 20 6f 66 20 52 65 69 6e |lgorithm| of Rein|
|00004490| 67 6f 6c 64 20 61 6e 64 | 20 54 69 6c 66 6f 72 64 |gold and| Tilford|
|000044a0| 20 28 68 65 72 65 61 66 | 74 65 72 20 63 61 6c 6c | (hereaf|ter call|
|000044b0| 65 64 20 60 60 74 68 65 | 20 52 54 7e 61 6c 67 6f |ed ``the| RT~algo|
|000044c0| 72 69 74 68 6d 27 27 29 | 20 20 20 0a 74 61 6b 65 |rithm'')| .take|
|000044d0| 73 20 61 20 6d 6f 64 75 | 6c 61 72 20 61 70 70 72 |s a modu|lar appr|
|000044e0| 6f 61 63 68 20 74 6f 20 | 74 68 65 20 20 20 20 20 |oach to |the |
|000044f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004500| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004510| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 70 6f 73 | | .pos|
|00004520| 69 74 69 6f 6e 69 6e 67 | 20 6f 66 20 6e 6f 64 65 |itioning| of node|
|00004530| 73 3a 20 54 68 65 20 72 | 65 6c 61 74 69 76 65 20 |s: The r|elative |
|00004540| 70 6f 73 69 74 69 6f 6e | 73 20 6f 66 20 74 68 65 |position|s of the|
|00004550| 20 6e 6f 64 65 73 20 69 | 6e 20 61 20 73 75 62 74 | nodes i|n a subt|
|00004560| 72 65 65 20 20 20 20 20 | 20 20 20 20 20 0a 61 72 |ree | .ar|
|00004570| 65 20 63 61 6c 63 75 6c | 61 74 65 64 20 69 6e 64 |e calcul|ated ind|
|00004580| 65 70 65 6e 64 65 6e 74 | 6c 79 20 66 72 6f 6d 20 |ependent|ly from |
|00004590| 74 68 65 20 72 65 73 74 | 20 6f 66 20 74 68 65 20 |the rest| of the |
|000045a0| 74 72 65 65 2e 20 41 66 | 74 65 72 20 74 68 65 20 |tree. Af|ter the |
|000045b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 72 | | .r|
|000045c0| 65 6c 61 74 69 76 65 20 | 70 6f 73 69 74 69 6f 6e |elative |position|
|000045d0| 73 20 6f 66 20 74 77 6f | 20 73 75 62 74 72 65 65 |s of two| subtree|
|000045e0| 73 20 68 61 76 65 20 62 | 65 65 6e 20 63 61 6c 63 |s have b|een calc|
|000045f0| 75 6c 61 74 65 64 2c 20 | 74 68 65 79 20 63 61 6e |ulated, |they can|
|00004600| 20 62 65 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | be | .|
|00004610| 6a 6f 69 6e 65 64 20 61 | 73 20 73 69 62 6c 69 6e |joined a|s siblin|
|00004620| 67 73 20 69 6e 20 61 20 | 6c 61 72 67 65 72 20 74 |gs in a |larger t|
|00004630| 72 65 65 20 62 79 20 70 | 6c 61 63 69 6e 67 20 74 |ree by p|lacing t|
|00004640| 68 65 6d 20 61 73 20 63 | 6c 6f 73 65 20 20 20 20 |hem as c|lose |
|00004650| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004660| 0a 74 6f 67 65 74 68 65 | 72 20 61 73 20 70 6f 73 |.togethe|r as pos|
|00004670| 73 69 62 6c 65 20 61 6e | 64 20 63 65 6e 74 65 72 |sible an|d center|
|00004680| 69 6e 67 20 74 68 65 20 | 70 61 72 65 6e 74 20 6e |ing the |parent n|
|00004690| 6f 64 65 20 61 62 6f 76 | 65 20 74 68 65 6d 2e 20 |ode abov|e them. |
|000046a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000046b0| 20 0a 49 6e 63 69 64 65 | 6e 74 61 6c 6c 79 2c 20 | .Incide|ntally, |
|000046c0| 74 68 65 20 6d 6f 64 75 | 6c 61 72 69 74 79 20 70 |the modu|larity p|
|000046d0| 72 69 6e 63 69 70 6c 65 | 20 69 73 20 74 68 65 20 |rinciple| is the |
|000046e0| 72 65 61 73 6f 6e 20 74 | 68 61 74 20 74 68 65 20 |reason t|hat the |
|000046f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004700| 20 20 0a 61 6c 67 6f 72 | 69 74 68 6d 20 66 61 69 | .algor|ithm fai|
|00004710| 6c 73 20 74 6f 20 66 75 | 6c 66 69 6c 6c 20 61 78 |ls to fu|lfill ax|
|00004720| 69 6f 6d 7e 36 3b 20 73 | 65 65 7e 5c 63 69 74 65 |iom~6; s|ee~\cite|
|00004730| 7b 43 6f 6d 70 6c 65 78 | 69 74 79 7d 2e 20 20 20 |{Complex|ity}. |
|00004740| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004750| 20 20 20 0a 54 77 6f 20 | 73 69 62 6c 69 6e 67 20 | .Two |sibling |
|00004760| 73 75 62 74 72 65 65 73 | 20 61 72 65 20 70 6c 61 |subtrees| are pla|
|00004770| 63 65 64 20 61 73 20 63 | 6c 6f 73 65 20 74 6f 67 |ced as c|lose tog|
|00004780| 65 74 68 65 72 20 61 73 | 20 70 6f 73 73 69 62 6c |ether as| possibl|
|00004790| 65 2c 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |e, | |
|000047a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 64 75 | | .du|
|000047b0| 72 69 6e 67 20 61 20 70 | 6f 73 74 6f 72 64 65 72 |ring a p|ostorder|
|000047c0| 20 74 72 61 76 65 72 73 | 61 6c 2c 20 61 73 20 66 | travers|al, as f|
|000047d0| 6f 6c 6c 6f 77 73 2e 20 | 41 74 20 65 61 63 68 20 |ollows. |At each |
|000047e0| 6e 6f 64 65 20 5c 76 61 | 72 7b 54 7d 2c 20 20 20 |node \va|r{T}, |
|000047f0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 69 | | .i|
|00004800| 6d 61 67 69 6e 65 20 74 | 68 61 74 20 69 74 73 20 |magine t|hat its |
|00004810| 74 77 6f 20 73 75 62 74 | 72 65 65 73 20 68 61 76 |two subt|rees hav|
|00004820| 65 20 62 65 65 6e 20 64 | 72 61 77 6e 20 61 6e 64 |e been d|rawn and|
|00004830| 20 63 75 74 20 6f 75 74 | 20 6f 66 20 70 61 70 65 | cut out| of pape|
|00004840| 72 20 61 6c 6f 6e 67 20 | 20 20 20 20 20 20 20 0a |r along | .|
|00004850| 74 68 65 69 72 20 63 6f | 6e 74 6f 75 72 73 2e 20 |their co|ntours. |
|00004860| 54 68 65 6e 2c 20 73 74 | 61 72 74 69 6e 67 20 77 |Then, st|arting w|
|00004870| 69 74 68 20 74 68 65 20 | 74 77 6f 20 73 75 62 74 |ith the |two subt|
|00004880| 72 65 65 73 20 73 75 70 | 65 72 69 6d 70 6f 73 65 |rees sup|erimpose|
|00004890| 64 20 61 74 20 74 68 65 | 69 72 20 20 20 20 20 20 |d at the|ir |
|000048a0| 0a 72 6f 6f 74 73 2c 20 | 6d 6f 76 65 20 74 68 65 |.roots, |move the|
|000048b0| 6d 20 61 70 61 72 74 20 | 75 6e 74 69 6c 20 61 20 |m apart |until a |
|000048c0| 6d 69 6e 69 6d 61 6c 20 | 61 67 72 65 65 64 20 75 |minimal |agreed u|
|000048d0| 70 6f 6e 20 64 69 73 74 | 61 6e 63 65 20 20 20 20 |pon dist|ance |
|000048e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000048f0| 20 0a 62 65 74 77 65 65 | 6e 20 74 68 65 20 74 72 | .betwee|n the tr|
|00004900| 65 65 73 20 69 73 20 6f | 62 74 61 69 6e 65 64 20 |ees is o|btained |
|00004910| 61 74 20 65 61 63 68 20 | 6c 65 76 65 6c 2e 20 54 |at each |level. T|
|00004920| 68 69 73 20 63 61 6e 20 | 62 65 20 64 6f 6e 65 20 |his can |be done |
|00004930| 67 72 61 64 75 61 6c 6c | 79 3a 20 20 20 20 20 20 |graduall|y: |
|00004940| 20 20 0a 49 6e 69 74 69 | 61 6c 6c 79 2c 20 74 68 | .Initi|ally, th|
|00004950| 65 69 72 20 72 6f 6f 74 | 73 20 61 72 65 20 73 65 |eir root|s are se|
|00004960| 70 61 72 61 74 65 64 20 | 62 79 20 73 6f 6d 65 20 |parated |by some |
|00004970| 61 67 72 65 65 64 20 75 | 70 6f 6e 20 6d 69 6e 69 |agreed u|pon mini|
|00004980| 6d 75 6d 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |mum | |
|00004990| 20 20 20 0a 64 69 73 74 | 61 6e 63 65 2e 20 54 68 | .dist|ance. Th|
|000049a0| 65 6e 2c 20 61 74 20 74 | 68 65 20 6e 65 78 74 20 |en, at t|he next |
|000049b0| 6c 6f 77 65 72 20 6c 65 | 76 65 6c 2c 20 20 20 20 |lower le|vel, |
|000049c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000049d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000049e0| 20 20 20 20 0a 74 68 65 | 79 20 61 72 65 20 70 75 | .the|y are pu|
|000049f0| 73 68 65 64 20 20 20 20 | 20 20 20 20 20 20 20 20 |shed | |
|00004a00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004a10| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004a20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004a30| 20 20 20 20 20 0a 61 70 | 61 72 74 20 75 6e 74 69 | .ap|art unti|
|00004a40| 6c 20 74 68 65 20 6d 69 | 6e 69 6d 75 6d 20 73 65 |l the mi|nimum se|
|00004a50| 70 61 72 61 74 69 6f 6e | 20 69 73 20 65 73 74 61 |paration| is esta|
|00004a60| 62 6c 69 73 68 65 64 20 | 74 68 65 72 65 2e 20 20 |blished |there. |
|00004a70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004a80| 20 20 20 20 20 20 0a 54 | 68 69 73 20 70 72 6f 63 | .T|his proc|
|00004a90| 65 73 73 20 69 73 20 63 | 6f 6e 74 69 6e 75 65 64 |ess is c|ontinued|
|00004aa0| 20 61 74 20 73 75 63 63 | 65 73 73 69 76 65 6c 79 | at succ|essively|
|00004ab0| 20 6c 6f 77 65 72 20 6c | 65 76 65 6c 73 20 75 6e | lower l|evels un|
|00004ac0| 74 69 6c 20 74 68 65 20 | 20 20 20 20 20 20 20 20 |til the | |
|00004ad0| 20 20 20 20 20 20 20 0a | 62 6f 74 74 6f 6d 20 6f | .|bottom o|
|00004ae0| 66 20 74 68 65 20 73 68 | 6f 72 74 65 72 20 73 75 |f the sh|orter su|
|00004af0| 62 74 72 65 65 20 69 73 | 20 72 65 61 63 68 65 64 |btree is| reached|
|00004b00| 2e 20 41 74 20 73 6f 6d | 65 20 6c 65 76 65 6c 73 |. At som|e levels|
|00004b10| 20 6e 6f 20 6d 6f 76 65 | 6d 65 6e 74 20 6d 61 79 | no move|ment may|
|00004b20| 20 62 65 20 20 20 20 20 | 0a 6e 65 63 65 73 73 61 | be |.necessa|
|00004b30| 72 79 3b 20 62 75 74 20 | 61 74 20 6e 6f 20 6c 65 |ry; but |at no le|
|00004b40| 76 65 6c 20 61 72 65 20 | 74 68 65 20 74 77 6f 20 |vel are |the two |
|00004b50| 73 75 62 74 72 65 65 73 | 20 6d 6f 76 65 64 20 63 |subtrees| moved c|
|00004b60| 6c 6f 73 65 72 20 20 20 | 20 20 20 20 20 20 20 20 |loser | |
|00004b70| 20 20 20 20 20 20 20 20 | 20 0a 74 6f 67 65 74 68 | | .togeth|
|00004b80| 65 72 2e 20 57 68 65 6e | 20 74 68 65 20 70 72 6f |er. When| the pro|
|00004b90| 63 65 73 73 20 69 73 20 | 63 6f 6d 70 6c 65 74 65 |cess is |complete|
|00004ba0| 2c 20 74 68 65 20 70 6f | 73 69 74 69 6f 6e 20 6f |, the po|sition o|
|00004bb0| 66 20 74 68 65 20 20 20 | 20 20 20 20 20 20 20 20 |f the | |
|00004bc0| 20 20 20 20 20 20 20 20 | 20 20 0a 73 75 62 74 72 | | .subtr|
|00004bd0| 65 65 73 20 69 73 20 66 | 69 78 65 64 20 72 65 6c |ees is f|ixed rel|
|00004be0| 61 74 69 76 65 20 74 6f | 20 74 68 65 69 72 20 70 |ative to| their p|
|00004bf0| 61 72 65 6e 74 2c 20 77 | 68 69 63 68 20 69 73 20 |arent, w|hich is |
|00004c00| 63 65 6e 74 65 72 65 64 | 20 6f 76 65 72 20 74 68 |centered| over th|
|00004c10| 65 6d 2e 20 20 20 20 20 | 20 20 20 0a 41 73 73 75 |em. | .Assu|
|00004c20| 72 65 64 20 74 68 61 74 | 20 74 68 65 20 73 75 62 |red that| the sub|
|00004c30| 74 72 65 65 73 20 77 69 | 6c 6c 20 6e 65 76 65 72 |trees wi|ll never|
|00004c40| 20 62 65 20 70 6c 61 63 | 65 64 20 63 6c 6f 73 65 | be plac|ed close|
|00004c50| 72 20 74 6f 67 65 74 68 | 65 72 2c 20 20 20 20 20 |r togeth|er, |
|00004c60| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 74 68 65 | | .the|
|00004c70| 20 70 6f 73 74 6f 72 64 | 65 72 20 74 72 61 76 65 | postord|er trave|
|00004c80| 72 73 61 6c 20 69 73 20 | 63 6f 6e 74 69 6e 75 65 |rsal is |continue|
|00004c90| 64 2e 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |d. | |
|00004ca0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004cb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 0a 20 20 | | . |
|00004cc0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004cd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004ce0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004cf0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004d00| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 0a 41 | | .A|
|00004d10| 20 6e 6f 6e 74 72 69 76 | 69 61 6c 20 69 6d 70 6c | nontriv|ial impl|
|00004d20| 65 6d 65 6e 74 61 74 69 | 6f 6e 20 6f 66 20 20 20 |ementati|on of |
|00004d30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004d40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004d50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 0a | | .|
|00004d60| 74 68 69 73 20 61 6c 67 | 6f 72 69 74 68 6d 20 68 |this alg|orithm h|
|00004d70| 61 73 20 62 65 65 6e 20 | 6f 62 74 61 69 6e 65 64 |as been |obtained|
|00004d80| 20 62 79 20 52 65 69 6e | 67 6f 6c 64 20 61 6e 64 | by Rein|gold and|
|00004d90| 20 54 69 6c 66 6f 72 64 | 20 74 68 61 74 20 72 75 | Tilford| that ru|
|00004da0| 6e 73 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |ns | |
|00004db0| 0a 69 6e 20 74 69 6d 65 | 20 24 5c 4f 28 4e 29 24 |.in time| $\O(N)$|
|00004dc0| 2c 20 77 68 65 72 65 20 | 24 4e 24 20 69 73 20 74 |, where |$N$ is t|
|00004dd0| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 20 20 20 20 |he numbe|r of |
|00004de0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004e00| 20 0a 6e 6f 64 65 73 20 | 6f 66 20 74 68 65 20 74 | .nodes |of the t|
|00004e10| 72 65 65 20 74 6f 20 62 | 65 20 64 72 61 77 6e 2e |ree to b|e drawn.|
|00004e20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004e30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004e40| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004e50| 20 20 0a 54 68 65 69 72 | 20 63 72 75 63 69 61 6c | .Their| crucial|
|00004e60| 20 69 64 65 61 20 69 73 | 20 74 6f 20 6b 65 65 70 | idea is| to keep|
|00004e70| 20 74 72 61 63 6b 20 6f | 66 20 74 68 65 20 63 6f | track o|f the co|
|00004e80| 6e 74 6f 75 72 20 6f 66 | 20 74 68 65 20 73 75 62 |ntour of| the sub|
|00004e90| 74 72 65 65 73 20 20 20 | 20 20 20 20 20 20 20 20 |trees | |
|00004ea0| 20 20 20 0a 62 79 20 73 | 70 65 63 69 61 6c 20 70 | .by s|pecial p|
|00004eb0| 6f 69 6e 74 65 72 73 2c | 20 63 61 6c 6c 65 64 20 |ointers,| called |
|00004ec0| 74 68 72 65 61 64 73 2c | 20 73 75 63 68 20 74 68 |threads,| such th|
|00004ed0| 61 74 20 77 68 65 6e 65 | 76 65 72 20 20 20 20 20 |at whene|ver |
|00004ee0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004ef0| 20 20 20 20 0a 74 77 6f | 20 73 75 62 74 72 65 65 | .two| subtree|
|00004f00| 73 20 61 72 65 20 6a 6f | 69 6e 65 64 2c 20 6f 6e |s are jo|ined, on|
|00004f10| 6c 79 20 74 68 65 20 20 | 20 20 20 20 20 20 20 20 |ly the | |
|00004f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004f30| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004f40| 20 20 20 20 20 0a 74 6f | 70 20 70 61 72 74 20 6f | .to|p part o|
|00004f50| 66 20 74 68 65 20 74 72 | 65 65 73 20 64 6f 77 6e |f the tr|ees down|
|00004f60| 20 74 6f 20 74 68 65 20 | 6c 6f 77 65 73 74 20 6c | to the |lowest l|
|00004f70| 65 76 65 6c 20 6f 66 20 | 74 68 65 20 20 20 20 20 |evel of |the |
|00004f80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004f90| 20 20 20 20 20 20 0a 73 | 6d 61 6c 6c 65 72 20 74 | .s|maller t|
|00004fa0| 72 65 65 20 6e 65 65 64 | 20 74 6f 20 62 65 20 74 |ree need| to be t|
|00004fb0| 61 6b 65 6e 20 69 6e 74 | 6f 20 61 63 63 6f 75 6e |aken int|o accoun|
|00004fc0| 74 2e 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |t. | |
|00004fd0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00004fe0| 0a 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00004ff0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005000| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005010| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005020| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005030| 20 0a 54 68 65 20 52 54 | 20 61 6c 67 6f 72 69 74 | .The RT| algorit|
|00005040| 68 6d 20 69 73 20 67 69 | 76 65 6e 20 69 6e 20 5c |hm is gi|ven in \|
|00005050| 63 69 74 65 7b 54 69 64 | 69 65 72 54 72 65 65 73 |cite{Tid|ierTrees|
|00005060| 7d 2e 0a 54 68 65 20 6e | 6f 64 65 73 20 61 72 65 |}..The n|odes are|
|00005070| 20 70 6f 73 69 74 69 6f | 6e 65 64 20 6f 6e 20 61 | positio|ned on a|
|00005080| 20 66 69 78 65 64 20 67 | 72 69 64 20 61 6e 64 20 | fixed g|rid and |
|00005090| 61 72 65 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |are | |
|000050a0| 0a 63 6f 6e 73 69 64 65 | 72 65 64 20 74 6f 20 68 |.conside|red to h|
|000050b0| 61 76 65 20 7a 65 72 6f | 20 77 69 64 74 68 2e 20 |ave zero| width. |
|000050c0| 4e 6f 20 6c 61 62 65 6c | 6c 69 6e 67 20 69 73 20 |No label|ling is |
|000050d0| 70 72 6f 76 69 64 65 64 | 2e 20 54 68 65 20 61 6c |provided|. The al|
|000050e0| 67 6f 72 69 74 68 6d 20 | 6f 6e 6c 79 20 20 20 20 |gorithm |only |
|000050f0| 20 0a 64 72 61 77 73 20 | 62 69 6e 61 72 79 20 74 | .draws |binary t|
|00005100| 72 65 65 73 2c 20 62 75 | 74 20 69 73 20 65 61 73 |rees, bu|t is eas|
|00005110| 69 6c 79 20 65 78 74 65 | 6e 64 61 62 6c 65 20 74 |ily exte|ndable t|
|00005120| 6f 20 6d 75 6c 74 69 77 | 61 79 20 74 72 65 65 73 |o multiw|ay trees|
|00005130| 2e 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. | |
|00005140| 20 20 0a 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | . | |
|00005150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005160| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005170| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005190| 20 20 20 0a 5c 73 65 63 | 74 69 6f 6e 7b 49 6d 70 | .\sec|tion{Imp|
|000051a0| 72 6f 76 69 6e 67 20 68 | 75 6d 61 6e 20 70 65 72 |roving h|uman per|
|000051b0| 63 65 70 74 69 6f 6e 20 | 6f 66 20 74 72 65 65 73 |ception |of trees|
|000051c0| 7d 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |} | |
|000051d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000051e0| 20 20 20 20 0a 0a 49 74 | 20 69 73 20 63 6f 6d 6d | ..It| is comm|
|000051f0| 6f 6e 20 75 6e 64 65 72 | 73 74 61 6e 64 69 6e 67 |on under|standing|
|00005200| 20 69 6e 20 62 6f 6f 6b | 20 64 65 73 69 67 6e 20 | in book| design |
|00005210| 74 68 61 74 20 61 65 73 | 74 68 65 74 69 63 73 20 |that aes|thetics |
|00005220| 61 6e 64 20 72 65 61 64 | 61 62 69 6c 69 74 79 0a |and read|ability.|
|00005230| 64 6f 6e 27 74 20 6e 65 | 63 65 73 73 61 72 69 6c |don't ne|cessaril|
|00005240| 79 20 63 6f 69 6e 63 69 | 64 65 2c 20 61 6e 64 2d |y coinci|de, and-|
|00005250| 2d 2d 61 73 20 4c 61 6d | 70 6f 72 74 20 28 5c 63 |--as Lam|port (\c|
|00005260| 69 74 65 7b 4c 61 54 65 | 58 7d 29 20 70 75 74 73 |ite{LaTe|X}) puts|
|00005270| 20 69 74 2d 2d 2d 25 0a | 62 6f 6f 6b 73 20 61 72 | it---%.|books ar|
|00005280| 65 20 6d 65 61 6e 74 20 | 74 6f 20 62 65 20 72 65 |e meant |to be re|
|00005290| 61 64 2c 20 6e 6f 74 20 | 74 6f 20 62 65 20 68 75 |ad, not |to be hu|
|000052a0| 6e 67 20 6f 6e 20 77 61 | 6c 6c 73 2e 20 54 68 65 |ng on wa|lls. The|
|000052b0| 72 65 66 6f 72 65 2c 20 | 72 65 61 64 61 62 69 6c |refore, |readabil|
|000052c0| 69 74 79 20 69 73 0a 6d | 6f 72 65 20 69 6d 70 6f |ity is.m|ore impo|
|000052d0| 72 74 61 6e 74 20 74 68 | 61 6e 20 61 65 73 74 68 |rtant th|an aesth|
|000052e0| 65 74 69 63 73 2e 0a 0a | 57 68 65 6e 20 69 74 20 |etics...|When it |
|000052f0| 63 6f 6d 65 73 20 74 6f | 20 74 72 65 65 20 64 72 |comes to| tree dr|
|00005300| 61 77 69 6e 67 73 2c 20 | 72 65 61 64 61 62 69 6c |awings, |readabil|
|00005310| 69 74 79 20 6d 65 61 6e | 73 20 74 68 61 74 20 74 |ity mean|s that t|
|00005320| 68 65 20 73 74 72 75 63 | 74 75 72 65 20 6f 66 0a |he struc|ture of.|
|00005330| 61 20 74 72 65 65 20 6d | 75 73 74 20 62 65 20 65 |a tree m|ust be e|
|00005340| 61 73 69 6c 79 20 72 65 | 63 6f 67 6e 69 7a 61 62 |asily re|cognizab|
|00005350| 6c 65 2e 20 54 68 69 73 | 20 63 72 69 74 65 72 69 |le. This| criteri|
|00005360| 6f 6e 20 69 73 20 6e 6f | 74 20 61 6c 77 61 79 73 |on is no|t always|
|00005370| 20 6d 65 74 0a 62 79 20 | 74 68 65 20 52 54 7e 61 | met.by |the RT~a|
|00005380| 6c 67 6f 72 69 74 68 6d | 2e 20 41 73 20 61 6e 20 |lgorithm|. As an |
|00005390| 65 78 61 6d 70 6c 65 2c | 20 74 68 65 72 65 20 61 |example,| there a|
|000053a0| 72 65 20 74 72 65 65 73 | 20 77 68 6f 73 65 20 73 |re trees| whose s|
|000053b0| 74 72 75 63 74 75 72 65 | 20 69 73 20 76 65 72 79 |tructure| is very|
|000053c0| 0a 64 69 66 66 65 72 65 | 6e 74 2c 20 74 68 65 20 |.differe|nt, the |
|000053d0| 6f 6e 6c 79 20 63 6f 6d | 6d 6f 6e 20 74 68 69 6e |only com|mon thin|
|000053e0| 67 20 62 65 69 6e 67 20 | 74 68 65 20 66 61 63 74 |g being |the fact|
|000053f0| 20 74 68 61 74 20 74 68 | 65 79 20 68 61 76 65 20 | that th|ey have |
|00005400| 74 68 65 20 73 61 6d 65 | 20 6e 75 6d 62 65 72 0a |the same| number.|
|00005410| 6f 66 20 6e 6f 64 65 73 | 20 61 74 20 65 61 63 68 |of nodes| at each|
|00005420| 20 6c 65 76 65 6c 2e 20 | 54 68 65 20 52 54 7e 61 | level. |The RT~a|
|00005430| 6c 67 6f 72 69 74 68 6d | 20 6d 69 67 68 74 20 61 |lgorithm| might a|
|00005440| 73 73 69 67 6e 20 69 64 | 65 6e 74 69 63 61 6c 20 |ssign id|entical |
|00005450| 70 6f 73 69 74 69 6f 6e | 73 20 74 6f 0a 74 68 65 |position|s to.the|
|00005460| 73 65 20 6e 6f 64 65 73 | 20 6d 61 6b 69 6e 67 20 |se nodes| making |
|00005470| 69 74 20 76 65 72 79 20 | 68 61 72 64 20 74 6f 20 |it very |hard to |
|00005480| 70 65 72 63 65 69 76 65 | 20 74 68 65 20 64 69 66 |perceive| the dif|
|00005490| 66 65 72 65 6e 74 20 73 | 74 72 75 63 74 75 72 65 |ferent s|tructure|
|000054a0| 73 2e 0a 48 65 6e 63 65 | 2c 20 77 65 20 68 61 76 |s..Hence|, we hav|
|000054b0| 65 20 6d 6f 64 69 66 69 | 65 64 20 74 68 65 20 52 |e modifi|ed the R|
|000054c0| 54 7e 61 6c 67 6f 72 69 | 74 68 6d 20 73 75 63 68 |T~algori|thm such|
|000054d0| 20 74 68 61 74 20 61 64 | 64 69 74 69 6f 6e 61 6c | that ad|ditional|
|000054e0| 20 77 68 69 74 65 20 73 | 70 61 63 65 0a 69 73 20 | white s|pace.is |
|000054f0| 69 6e 73 65 72 74 65 64 | 20 62 65 74 77 65 65 6e |inserted| between|
|00005500| 20 73 75 62 74 72 65 65 | 73 20 6f 66 20 0a 5c 65 | subtree|s of .\e|
|00005510| 6d 70 68 7b 73 69 67 6e | 69 66 69 63 61 6e 74 7d |mph{sign|ificant}|
|00005520| 20 6e 6f 64 65 73 2e 20 | 48 65 72 65 20 61 20 62 | nodes. |Here a b|
|00005530| 69 6e 61 72 79 20 6e 6f | 64 65 20 0a 69 73 20 63 |inary no|de .is c|
|00005540| 61 6c 6c 65 64 20 73 69 | 67 6e 69 66 69 63 61 6e |alled si|gnifican|
|00005550| 74 20 69 66 20 74 68 65 | 20 6d 69 6e 69 6d 75 6d |t if the| minimum|
|00005560| 20 64 69 73 74 61 6e 63 | 65 0a 62 65 74 77 65 65 | distanc|e.betwee|
|00005570| 6e 20 69 74 73 20 74 77 | 6f 20 73 75 62 74 72 65 |n its tw|o subtre|
|00005580| 65 73 20 69 73 20 74 61 | 6b 65 6e 20 5c 65 6d 70 |es is ta|ken \emp|
|00005590| 68 7b 62 65 6c 6f 77 7d | 20 74 68 65 69 72 20 72 |h{below}| their r|
|000055a0| 6f 6f 74 20 6c 65 76 65 | 6c 2e 0a 53 65 74 74 69 |oot leve|l..Setti|
|000055b0| 6e 67 20 74 68 65 20 61 | 6d 6f 75 6e 74 20 6f 66 |ng the a|mount of|
|000055c0| 20 61 64 64 69 74 69 6f | 6e 61 6c 20 77 68 69 74 | additio|nal whit|
|000055d0| 65 20 73 70 61 63 65 20 | 74 6f 20 7a 65 72 6f 20 |e space |to zero |
|000055e0| 72 65 74 61 69 6e 73 20 | 74 68 65 20 6f 72 69 67 |retains |the orig|
|000055f0| 69 6e 61 6c 20 52 54 7e | 25 0a 70 6c 61 63 65 6d |inal RT~|%.placem|
|00005600| 65 6e 74 2e 20 54 68 65 | 20 65 66 66 65 63 74 20 |ent. The| effect |
|00005610| 6f 66 20 68 61 76 69 6e | 67 20 6e 6f 6e 7a 65 72 |of havin|g nonzer|
|00005620| 6f 20 61 64 64 69 74 69 | 6f 6e 61 6c 20 77 68 69 |o additi|onal whi|
|00005630| 74 65 20 73 70 61 63 65 | 20 62 65 74 77 65 65 6e |te space| between|
|00005640| 20 0a 74 68 65 20 73 75 | 62 74 72 65 65 73 20 6f | .the su|btrees o|
|00005650| 66 20 73 69 67 6e 69 66 | 69 63 61 6e 74 0a 6e 6f |f signif|icant.no|
|00005660| 64 65 73 20 69 73 20 69 | 6c 6c 75 73 74 72 61 74 |des is i|llustrat|
|00005670| 65 64 20 69 6e 20 5c 66 | 69 67 7b 61 64 64 73 70 |ed in \f|ig{addsp|
|00005680| 61 63 65 7d 20 2e 0a 0a | 41 6e 6f 74 68 65 72 20 |ace} ...|Another |
|00005690| 66 65 61 74 75 72 65 20 | 77 65 20 68 61 76 65 20 |feature |we have |
|000056a0| 61 64 64 65 64 20 74 6f | 20 74 68 65 20 52 54 7e |added to| the RT~|
|000056b0| 61 6c 67 6f 72 69 74 68 | 6d 73 20 69 73 20 74 68 |algorith|ms is th|
|000056c0| 65 20 70 6f 73 73 69 62 | 69 6c 69 74 79 20 74 6f |e possib|ility to|
|000056d0| 20 64 72 61 77 0a 61 6e | 20 75 6e 65 78 74 65 6e | draw.an| unexten|
|000056e0| 64 65 64 20 62 69 6e 61 | 72 79 20 74 72 65 65 20 |ded bina|ry tree |
|000056f0| 77 69 74 68 20 74 68 65 | 20 73 61 6d 65 20 70 6c |with the| same pl|
|00005700| 61 63 65 6d 65 6e 74 20 | 6f 66 20 6e 6f 64 65 73 |acement |of nodes|
|00005710| 20 61 73 20 69 74 73 0a | 61 73 73 6f 63 69 61 74 | as its.|associat|
|00005720| 65 64 20 65 78 74 65 6e | 64 65 64 20 76 65 72 73 |ed exten|ded vers|
|00005730| 69 6f 6e 2e 20 57 65 20 | 64 65 66 69 6e 65 20 74 |ion. We |define t|
|00005740| 68 65 20 5c 65 6d 70 68 | 7b 61 73 73 6f 63 69 61 |he \emph|{associa|
|00005750| 74 65 64 20 65 78 74 65 | 6e 64 65 64 20 76 65 72 |ted exte|nded ver|
|00005760| 73 69 6f 6e 7d 0a 6f 66 | 20 61 20 62 69 6e 61 72 |sion}.of| a binar|
|00005770| 79 20 74 72 65 65 20 74 | 6f 20 62 65 20 74 68 65 |y tree t|o be the|
|00005780| 20 62 69 6e 61 72 79 20 | 74 72 65 65 20 6f 62 74 | binary |tree obt|
|00005790| 61 69 6e 65 64 20 62 79 | 20 72 65 70 6c 61 63 69 |ained by| replaci|
|000057a0| 6e 67 20 65 61 63 68 20 | 65 6d 70 74 79 20 73 75 |ng each |empty su|
|000057b0| 62 74 72 65 65 0a 68 61 | 76 69 6e 67 20 61 20 6e |btree.ha|ving a n|
|000057c0| 6f 6e 65 6d 70 74 79 20 | 73 69 62 6c 69 6e 67 20 |onempty |sibling |
|000057d0| 77 69 74 68 20 61 20 73 | 75 62 74 72 65 65 20 63 |with a s|ubtree c|
|000057e0| 6f 6e 73 69 73 74 69 6e | 67 20 6f 66 20 6f 6e 65 |onsistin|g of one|
|000057f0| 20 6e 6f 64 65 2e 20 54 | 68 69 73 20 66 65 61 74 | node. T|his feat|
|00005800| 75 72 65 0a 61 6c 73 6f | 20 6d 61 6b 65 73 20 74 |ure.also| makes t|
|00005810| 68 65 20 73 74 72 75 63 | 74 75 72 65 20 6f 66 20 |he struc|ture of |
|00005820| 61 20 74 72 65 65 20 6d | 6f 72 65 20 70 72 6f 6d |a tree m|ore prom|
|00005830| 69 6e 65 6e 74 3b 20 73 | 65 65 20 5c 66 69 67 7b |inent; s|ee \fig{|
|00005840| 65 78 74 65 6e 64 65 64 | 7d 2e 0a 0a 5c 62 65 67 |extended|}...\beg|
|00005850| 69 6e 7b 46 69 67 75 72 | 65 7d 0a 5c 63 65 6e 74 |in{Figur|e}.\cent|
|00005860| 65 72 69 6e 67 0a 5c 6c | 65 61 76 65 76 6d 6f 64 |ering.\l|eavevmod|
|00005870| 65 5c 6e 6f 69 6e 64 65 | 6e 74 20 20 20 20 20 20 |e\noinde|nt |
|00005880| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005890| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000058a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000058b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000058c0| 0a 5c 62 65 67 69 6e 7b | 54 72 65 65 7d 20 0a 5c |.\begin{|Tree} .\|
|000058d0| 65 5c 69 6c 5c 65 5c 65 | 5c 69 5c 69 5c 69 6c 20 |e\il\e\e|\i\i\il |
|000058e0| 25 20 74 68 65 20 6c 65 | 66 74 20 73 75 62 74 72 |% the le|ft subtr|
|000058f0| 65 65 0a 5c 65 5c 69 72 | 5c 69 6c 20 25 20 74 68 |ee.\e\ir|\il % th|
|00005900| 65 20 72 69 67 68 74 20 | 73 75 62 74 72 65 65 20 |e right |subtree |
|00005910| 20 0a 5c 69 0a 5c 65 6e | 64 7b 54 72 65 65 7d 0a | .\i.\en|d{Tree}.|
|00005920| 5c 68 73 6b 69 70 5c 6c | 65 66 74 64 69 73 74 5c |\hskip\l|eftdist\|
|00005930| 62 6f 78 5c 54 65 58 54 | 72 65 65 5c 68 73 6b 69 |box\TeXT|ree\hski|
|00005940| 70 5c 72 69 67 68 74 64 | 69 73 74 5c 71 71 75 61 |p\rightd|ist\qqua|
|00005950| 64 0a 5c 62 65 67 69 6e | 7b 54 72 65 65 7d 0a 5c |d.\begin|{Tree}.\|
|00005960| 65 5c 69 6c 5c 69 6c 5c | 69 6c 20 25 20 74 68 65 |e\il\il\|il % the|
|00005970| 20 6c 65 66 74 20 73 75 | 62 74 72 65 65 0a 5c 65 | left su|btree.\e|
|00005980| 5c 65 5c 69 5c 65 5c 69 | 5c 69 6c 20 25 20 74 68 |\e\i\e\i|\il % th|
|00005990| 65 20 72 69 67 68 74 20 | 73 75 62 74 72 65 65 0a |e right |subtree.|
|000059a0| 5c 69 0a 5c 65 6e 64 7b | 54 72 65 65 7d 20 20 20 |\i.\end{|Tree} |
|000059b0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000059c0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000059d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000059e0| 20 20 20 20 20 20 20 20 | 20 20 20 20 0a 5c 68 73 | | .\hs|
|000059f0| 6b 69 70 5c 6c 65 66 74 | 64 69 73 74 5c 62 6f 78 |kip\left|dist\box|
|00005a00| 5c 54 65 58 54 72 65 65 | 5c 68 73 6b 69 70 5c 72 |\TeXTree|\hskip\r|
|00005a10| 69 67 68 74 64 69 73 74 | 5c 71 71 75 61 64 0a 5c |ightdist|\qquad.\|
|00005a20| 61 64 64 73 40 70 31 30 | 70 74 0a 5c 62 65 67 69 |adds@p10|pt.\begi|
|00005a30| 6e 7b 54 72 65 65 7d 0a | 5c 65 5c 69 6c 5c 65 5c |n{Tree}.|\e\il\e\|
|00005a40| 65 5c 69 5c 6e 6f 64 65 | 7b 5c 74 79 70 65 7b 64 |e\i\node|{\type{d|
|00005a50| 6f 74 7d 5c 6c 66 74 7b | 24 5c 6c 6f 6e 67 72 69 |ot}\lft{|$\longri|
|00005a60| 67 68 74 61 72 72 6f 77 | 24 7d 7d 5c 69 6c 20 25 |ghtarrow|$}}\il %|
|00005a70| 20 74 68 65 20 6c 65 66 | 74 20 73 75 62 74 72 65 | the lef|t subtre|
|00005a80| 65 0a 5c 65 5c 69 72 5c | 69 6c 20 25 20 74 68 65 |e.\e\ir\|il % the|
|00005a90| 20 72 69 67 68 74 20 73 | 75 62 74 72 65 65 20 20 | right s|ubtree |
|00005aa0| 0a 5c 6e 6f 64 65 7b 5c | 74 79 70 65 7b 64 6f 74 |.\node{\|type{dot|
|00005ab0| 7d 5c 6c 66 74 7b 24 5c | 6c 6f 6e 67 72 69 67 68 |}\lft{$\|longrigh|
|00005ac0| 74 61 72 72 6f 77 24 7d | 7d 0a 5c 65 6e 64 7b 54 |tarrow$}|}.\end{T|
|00005ad0| 72 65 65 7d 0a 5c 68 73 | 6b 69 70 5c 6c 65 66 74 |ree}.\hs|kip\left|
|00005ae0| 64 69 73 74 5c 62 6f 78 | 5c 54 65 58 54 72 65 65 |dist\box|\TeXTree|
|00005af0| 5c 68 73 6b 69 70 5c 72 | 69 67 68 74 64 69 73 74 |\hskip\r|ightdist|
|00005b00| 5c 71 71 75 61 64 0a 5c | 62 65 67 69 6e 7b 54 72 |\qquad.\|begin{Tr|
|00005b10| 65 65 7d 0a 5c 65 5c 69 | 6c 5c 69 6c 5c 69 6c 20 |ee}.\e\i|l\il\il |
|00005b20| 25 20 74 68 65 20 6c 65 | 66 74 20 73 75 62 74 72 |% the le|ft subtr|
|00005b30| 65 65 0a 5c 65 5c 65 5c | 69 5c 65 5c 69 5c 69 6c |ee.\e\e\|i\e\i\il|
|00005b40| 20 25 20 74 68 65 20 72 | 69 67 68 74 20 73 75 62 | % the r|ight sub|
|00005b50| 74 72 65 65 0a 5c 6e 6f | 64 65 7b 5c 74 79 70 65 |tree.\no|de{\type|
|00005b60| 7b 64 6f 74 7d 5c 6c 66 | 74 7b 24 5c 6c 6f 6e 67 |{dot}\lf|t{$\long|
|00005b70| 72 69 67 68 74 61 72 72 | 6f 77 24 7d 7d 0a 5c 65 |rightarr|ow$}}.\e|
|00005b80| 6e 64 7b 54 72 65 65 7d | 20 20 20 20 20 20 20 20 |nd{Tree}| |
|00005b90| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005ba0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005bb0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005bc0| 20 20 20 20 20 20 20 0a | 5c 68 73 6b 69 70 5c 6c | .|\hskip\l|
|00005bd0| 65 66 74 64 69 73 74 5c | 62 6f 78 5c 54 65 58 54 |eftdist\|box\TeXT|
|00005be0| 72 65 65 5c 68 73 6b 69 | 70 5c 72 69 67 68 74 64 |ree\hski|p\rightd|
|00005bf0| 69 73 74 5c 0a 5c 61 64 | 64 73 40 70 30 70 74 0a |ist\.\ad|ds@p0pt.|
|00005c00| 0a 5c 63 61 70 74 69 6f | 6e 7b 54 68 65 20 66 69 |.\captio|n{The fi|
|00005c10| 72 73 74 20 74 77 6f 20 | 74 72 65 65 73 20 67 65 |rst two |trees ge|
|00005c20| 74 20 74 68 65 20 73 61 | 6d 65 20 70 6c 61 63 65 |t the sa|me place|
|00005c30| 6d 65 6e 74 20 6f 66 20 | 74 68 65 69 72 20 6e 6f |ment of |their no|
|00005c40| 64 65 73 0a 62 79 20 74 | 68 65 20 52 54 7e 61 6c |des.by t|he RT~al|
|00005c50| 67 6f 72 69 74 68 6d 2c | 20 61 6c 74 68 6f 75 67 |gorithm,| althoug|
|00005c60| 68 20 74 68 65 20 73 74 | 72 75 63 74 75 72 65 20 |h the st|ructure |
|00005c70| 6f 66 20 74 68 65 20 74 | 77 6f 20 74 72 65 65 73 |of the t|wo trees|
|00005c80| 20 69 73 20 76 65 72 79 | 20 64 69 66 66 65 72 65 | is very| differe|
|00005c90| 6e 74 2e 0a 54 68 65 20 | 61 6c 74 65 72 6e 61 74 |nt..The |alternat|
|00005ca0| 69 76 65 20 64 72 61 77 | 69 6e 67 73 20 68 69 67 |ive draw|ings hig|
|00005cb0| 68 6c 69 67 68 74 20 74 | 68 65 20 73 74 72 75 63 |hlight t|he struc|
|00005cc0| 74 75 72 65 20 6f 66 20 | 74 68 65 20 74 72 65 65 |ture of |the tree|
|00005cd0| 73 20 62 79 20 61 64 64 | 69 6e 67 0a 61 64 64 69 |s by add|ing.addi|
|00005ce0| 74 69 6f 6e 61 6c 20 77 | 68 69 74 65 20 73 70 61 |tional w|hite spa|
|00005cf0| 63 65 20 62 65 74 77 65 | 65 6e 20 74 68 65 20 73 |ce betwe|en the s|
|00005d00| 75 62 74 72 65 65 73 20 | 6f 66 20 0a 28 24 5c 6c |ubtrees |of .($\l|
|00005d10| 6f 6e 67 72 69 67 68 74 | 61 72 72 6f 77 24 29 20 |ongright|arrow$) |
|00005d20| 73 69 67 6e 69 66 69 63 | 61 6e 74 20 6e 6f 64 65 |signific|ant node|
|00005d30| 73 2e 7d 0a 5c 6c 61 62 | 65 6c 7b 61 64 64 73 70 |s.}.\lab|el{addsp|
|00005d40| 61 63 65 7d 20 20 20 20 | 20 20 20 20 20 20 20 20 |ace} | |
|00005d50| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005d60| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005d70| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005d80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00005d90| 20 20 20 20 0a 5c 65 6e | 64 7b 46 69 67 75 72 65 | .\en|d{Figure|
|00005da0| 7d 20 0a 0a 5c 62 65 67 | 69 6e 7b 46 69 67 75 72 |} ..\beg|in{Figur|
|00005db0| 65 7d 0a 5c 63 65 6e 74 | 65 72 69 6e 67 0a 5c 6c |e}.\cent|ering.\l|
|00005dc0| 65 61 76 65 76 6d 6f 64 | 65 5c 6e 6f 69 6e 64 65 |eavevmod|e\noinde|
|00005dd0| 6e 74 0a 5c 62 65 67 69 | 6e 7b 54 72 65 65 7d 0a |nt.\begi|n{Tree}.|
|00005de0| 5c 65 5c 65 5c 69 5c 69 | 6c 5c 65 5c 65 5c 69 5c |\e\e\i\i|l\e\e\i\|
|00005df0| 69 0a 5c 65 6e 64 7b 54 | 72 65 65 7d 0a 5c 68 73 |i.\end{T|ree}.\hs|
|00005e00| 6b 69 70 5c 6c 65 66 74 | 64 69 73 74 5c 62 6f 78 |kip\left|dist\box|
|00005e10| 5c 54 65 58 54 72 65 65 | 5c 68 73 6b 69 70 5c 72 |\TeXTree|\hskip\r|
|00005e20| 69 67 68 74 64 69 73 74 | 5c 71 71 75 61 64 0a 5c |ightdist|\qquad.\|
|00005e30| 62 65 67 69 6e 7b 54 72 | 65 65 7d 0a 5c 65 5c 65 |begin{Tr|ee}.\e\e|
|00005e40| 5c 69 5c 65 5c 69 5c 65 | 5c 69 72 5c 69 0a 5c 65 |\i\e\i\e|\ir\i.\e|
|00005e50| 6e 64 7b 54 72 65 65 7d | 0a 5c 68 73 6b 69 70 5c |nd{Tree}|.\hskip\|
|00005e60| 6c 65 66 74 64 69 73 74 | 5c 62 6f 78 5c 54 65 58 |leftdist|\box\TeX|
|00005e70| 54 72 65 65 5c 68 73 6b | 69 70 5c 72 69 67 68 74 |Tree\hsk|ip\right|
|00005e80| 64 69 73 74 5c 71 71 75 | 61 64 0a 5c 65 78 74 65 |dist\qqu|ad.\exte|
|00005e90| 6e 64 65 64 0a 5c 62 65 | 67 69 6e 7b 54 72 65 65 |nded.\be|gin{Tree|
|00005ea0| 7d 0a 5c 65 5c 65 5c 69 | 5c 69 6c 5c 65 5c 65 5c |}.\e\e\i|\il\e\e\|
|00005eb0| 69 5c 69 0a 5c 65 6e 64 | 7b 54 72 65 65 7d 0a 5c |i\i.\end|{Tree}.\|
|00005ec0| 68 73 6b 69 70 5c 6c 65 | 66 74 64 69 73 74 5c 62 |hskip\le|ftdist\b|
|00005ed0| 6f 78 5c 54 65 58 54 72 | 65 65 5c 68 73 6b 69 70 |ox\TeXTr|ee\hskip|
|00005ee0| 5c 72 69 67 68 74 64 69 | 73 74 5c 71 71 75 61 64 |\rightdi|st\qquad|
|00005ef0| 0a 5c 62 65 67 69 6e 7b | 54 72 65 65 7d 0a 5c 65 |.\begin{|Tree}.\e|
|00005f00| 5c 65 5c 69 5c 65 5c 69 | 5c 65 5c 69 72 5c 69 0a |\e\i\e\i|\e\ir\i.|
|00005f10| 5c 65 6e 64 7b 54 72 65 | 65 7d 0a 5c 68 73 6b 69 |\end{Tre|e}.\hski|
|00005f20| 70 5c 6c 65 66 74 64 69 | 73 74 5c 62 6f 78 5c 54 |p\leftdi|st\box\T|
|00005f30| 65 58 54 72 65 65 5c 68 | 73 6b 69 70 5c 72 69 67 |eXTree\h|skip\rig|
|00005f40| 68 74 64 69 73 74 5c 5c | 0a 5c 6e 6f 65 78 74 65 |htdist\\|.\noexte|
|00005f50| 6e 64 65 64 0a 5c 62 65 | 67 69 6e 7b 54 72 65 65 |nded.\be|gin{Tree|
|00005f60| 7d 0a 5c 65 5c 65 5c 69 | 5c 65 5c 69 5c 65 5c 65 |}.\e\e\i|\e\i\e\e|
|00005f70| 5c 69 5c 69 0a 5c 65 6e | 64 7b 54 72 65 65 7d 0a |\i\i.\en|d{Tree}.|
|00005f80| 5c 68 73 6b 69 70 5c 6c | 65 66 74 64 69 73 74 5c |\hskip\l|eftdist\|
|00005f90| 62 6f 78 5c 54 65 58 54 | 72 65 65 5c 68 73 6b 69 |box\TeXT|ree\hski|
|00005fa0| 70 5c 72 69 67 68 74 64 | 69 73 74 5c 20 20 0a 5c |p\rightd|ist\ .\|
|00005fb0| 63 61 70 74 69 6f 6e 7b | 49 6e 20 74 68 65 20 66 |caption{|In the f|
|00005fc0| 69 72 73 74 20 74 77 6f | 20 64 72 61 77 69 6e 67 |irst two| drawing|
|00005fd0| 73 2c 20 74 68 65 20 52 | 54 7e 61 6c 67 6f 72 69 |s, the R|T~algori|
|00005fe0| 74 68 6d 20 61 73 73 69 | 67 6e 73 20 74 68 65 20 |thm assi|gns the |
|00005ff0| 73 61 6d 65 20 70 6c 61 | 63 65 6d 65 6e 74 20 0a |same pla|cement .|
|00006000| 74 6f 20 74 68 65 20 6e | 6f 64 65 73 20 6f 66 20 |to the n|odes of |
|00006010| 74 77 6f 20 74 72 65 65 | 73 20 61 6c 74 68 6f 75 |two tree|s althou|
|00006020| 67 68 20 74 68 65 69 72 | 20 73 74 72 75 63 74 75 |gh their| structu|
|00006030| 72 65 20 69 73 20 76 65 | 72 79 20 64 69 66 66 65 |re is ve|ry diffe|
|00006040| 72 65 6e 74 2e 20 54 68 | 65 20 6d 6f 64 69 66 69 |rent. Th|e modifi|
|00006050| 65 64 0a 52 54 7e 61 6c | 67 6f 72 69 74 68 6d 73 |ed.RT~al|gorithms|
|00006060| 20 68 69 67 68 6c 69 67 | 68 74 73 20 74 68 65 20 | highlig|hts the |
|00006070| 73 74 72 75 63 74 75 72 | 65 20 6f 66 20 74 68 65 |structur|e of the|
|00006080| 20 74 72 65 65 73 20 62 | 79 20 6f 70 74 69 6f 6e | trees b|y option|
|00006090| 61 6c 6c 79 0a 64 72 61 | 77 69 6e 67 20 74 68 65 |ally.dra|wing the|
|000060a0| 6d 20 6c 69 6b 65 20 74 | 68 65 69 72 20 65 78 74 |m like t|heir ext|
|000060b0| 65 6e 64 65 64 0a 63 6f | 75 6e 74 65 72 70 61 72 |ended.co|unterpar|
|000060c0| 74 2c 20 77 68 69 63 68 | 20 69 73 20 67 69 76 65 |t, which| is give|
|000060d0| 6e 20 69 6e 20 74 68 65 | 20 73 65 63 6f 6e 64 20 |n in the| second |
|000060e0| 72 6f 77 2e 7d 0a 5c 6c | 61 62 65 6c 7b 65 78 74 |row.}.\l|abel{ext|
|000060f0| 65 6e 64 65 64 7d 0a 5c | 65 6e 64 7b 46 69 67 75 |ended}.\|end{Figu|
|00006100| 72 65 7d 0a 0a 0a 5c 73 | 65 63 74 69 6f 6e 7b 54 |re}...\s|ection{T|
|00006110| 72 65 65 73 20 69 6e 20 | 61 20 64 6f 63 75 6d 65 |rees in |a docume|
|00006120| 6e 74 20 70 72 65 70 61 | 72 61 74 69 6f 6e 20 65 |nt prepa|ration e|
|00006130| 6e 76 69 72 6f 6e 6d 65 | 6e 74 7d 20 20 20 20 20 |nvironme|nt} |
|00006140| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00006150| 20 20 20 20 20 20 0a 20 | 20 20 20 20 20 20 20 20 | . | |
|00006160| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00006170| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00006180| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00006190| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000061a0| 20 20 20 20 20 20 20 0a | 44 72 61 77 69 6e 67 73 | .|Drawings|
|000061b0| 20 6f 66 20 74 72 65 65 | 73 20 75 73 75 61 6c 6c | of tree|s usuall|
|000061c0| 79 20 64 6f 6e 27 74 20 | 63 6f 6d 65 20 61 6c 6f |y don't |come alo|
|000061d0| 6e 65 2c 20 62 75 74 20 | 61 72 65 20 69 6e 63 6c |ne, but |are incl|
|000061e0| 75 64 65 64 20 69 6e 20 | 73 6f 6d 65 20 74 65 78 |uded in |some tex|
|000061f0| 74 20 20 20 20 20 20 20 | 0a 77 68 69 63 68 20 69 |t |.which i|
|00006200| 73 20 69 74 73 65 6c 66 | 20 74 79 70 65 73 65 74 |s itself| typeset|
|00006210| 20 62 79 20 61 20 74 65 | 78 74 20 70 72 6f 63 65 | by a te|xt proce|
|00006220| 73 73 69 6e 67 20 73 79 | 73 74 65 6d 2e 20 54 68 |ssing sy|stem. Th|
|00006230| 65 72 65 66 6f 72 65 2c | 20 61 20 74 79 70 69 63 |erefore,| a typic|
|00006240| 61 6c 20 20 20 20 20 20 | 0a 73 63 65 6e 61 72 69 |al |.scenari|
|00006250| 6f 20 69 73 20 61 20 70 | 69 70 65 20 6f 66 20 74 |o is a p|ipe of t|
|00006260| 68 72 65 65 20 73 74 61 | 67 65 73 2e 20 46 69 72 |hree sta|ges. Fir|
|00006270| 73 74 20 63 6f 6d 65 73 | 20 74 68 65 20 74 72 65 |st comes| the tre|
|00006280| 65 20 64 72 61 77 69 6e | 67 20 20 20 20 20 20 20 |e drawin|g |
|00006290| 20 20 20 20 20 20 0a 70 | 72 6f 67 72 61 6d 20 77 | .p|rogram w|
|000062a0| 68 69 63 68 20 63 61 6c | 63 75 6c 61 74 65 73 20 |hich cal|culates |
|000062b0| 74 68 65 20 70 6f 73 69 | 74 69 6f 6e 69 6e 67 20 |the posi|tioning |
|000062c0| 6f 66 20 74 68 65 20 6e | 6f 64 65 73 20 6f 66 20 |of the n|odes of |
|000062d0| 74 68 65 20 74 72 65 65 | 20 74 6f 20 20 20 20 20 |the tree| to |
|000062e0| 20 20 20 20 20 20 20 0a | 62 65 20 64 72 61 77 6e | .|be drawn|
|000062f0| 20 61 6e 64 20 6f 75 74 | 70 75 74 73 20 61 20 64 | and out|puts a d|
|00006300| 65 73 63 72 69 70 74 69 | 6f 6e 20 6f 66 20 74 68 |escripti|on of th|
|00006310| 65 20 74 72 65 65 20 64 | 72 61 77 69 6e 67 20 69 |e tree d|rawing i|
|00006320| 6e 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |n | |
|00006330| 20 20 20 20 20 20 20 20 | 0a 73 6f 6d 65 20 67 72 | |.some gr|
|00006340| 61 70 68 69 63 73 20 6c | 61 6e 67 75 61 67 65 3b |aphics l|anguage;|
|00006350| 20 6e 65 78 74 20 63 6f | 6d 65 73 20 61 20 67 72 | next co|mes a gr|
|00006360| 61 70 68 69 63 73 20 73 | 79 73 74 65 6d 20 77 68 |aphics s|ystem wh|
|00006370| 69 63 68 20 74 72 61 6e | 73 66 6f 72 6d 73 20 74 |ich tran|sforms t|
|00006380| 68 69 73 20 20 20 20 20 | 20 0a 64 65 73 63 72 69 |his | .descri|
|00006390| 70 74 69 6f 6e 20 69 6e | 74 6f 20 61 6e 20 69 6e |ption in|to an in|
|000063a0| 74 65 72 6d 65 64 69 61 | 74 65 20 6c 61 6e 67 75 |termedia|te langu|
|000063b0| 61 67 65 20 77 68 69 63 | 68 20 63 61 6e 20 62 65 |age whic|h can be|
|000063c0| 20 69 6e 74 65 72 70 72 | 65 74 65 64 20 62 79 20 | interpr|eted by |
|000063d0| 74 68 65 20 6f 75 74 70 | 75 74 0a 64 65 76 69 63 |the outp|ut.devic|
|000063e0| 65 3b 20 61 6e 64 20 66 | 69 6e 61 6c 6c 79 20 63 |e; and f|inally c|
|000063f0| 6f 6d 65 73 20 74 68 65 | 20 20 20 20 20 20 20 20 |omes the| |
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.